searchRange

1855 단어
34.                      
                nums,       target。                     。

             O(log n)   。

           ,   [-1, -1]。

   1:

  : nums = [5,7,7,8,8,10], target = 8
  : [3,4]
   2:

  : nums = [5,7,7,8,8,10], target = 6
  : [-1,-1]
    102,556    258,038
class Solution {
   public int[] searchRange(int[] nums, int target) {
        //                   
        int[] res = {-1, -1};
        int len = nums.length;
        int leftB = leftBound(nums, target);
        if(leftB == -1) return res;
        res[0] = leftB;
        res[1] = rightBound(nums, target);
        return res;
    }
    private int leftBound(int[] nums, int target){
        int len = nums.length;
        int left = 0; int right = len-1;
        //      left = right+1;
        while(left <= right){
            int mid = (left+right)/2;
            if(target < nums[mid]){
                right = mid-1;
            }else if(target > nums[mid]){
                left = mid+1;
            }else{
                // mid = right+1 = left
                right = mid-1;
            }
        }
        if(left >= len || nums[left]!=target)
            return -1;
        return left;
    }
    private int rightBound(int[] nums, int target){
        int len = nums.length;
        int left = 0; int right = len-1;
        //      left = right+1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if (target < nums[mid]) {
                right = mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                // mid = left-1 = right
                left = mid+1;
            }
        }
        if(right<0 || nums[right]!= target){
            return -1;
        }
        return right;
    }
}

좋은 웹페이지 즐겨찾기