题目

image.png

思路

  • 就是二分法的左边界和右边界而已

    代码

    1.   //1.遍历版本1
    2.   public int[] searchRange(int[] nums, int target) {
    3.       int[] res = new int[]{-1, -1};
    4.       if (nums.length == 0) return res;
    5.       int i = 0, j = nums.length, index = -1;
    6.       //左边界
    7.       while (i < j) {
    8.           index = (i + j) / 2;
    9.           if (target == nums[index]) {
    10.               i = index + 1;
    11.               res[1] = index;
    12.           } else if (target > nums[index]) {
    13.               i = index + 1;
    14.           } else if (target < nums[index]) {
    15.               j = index;
    16.           }
    17.       }
    18.       i = 0; j = nums.length;
    19.       //右边界
    20.       while (i < j) {
    21.           index = (i + j) / 2;
    22.           if (target == nums[index]) {
    23.               j = index;
    24.               res[0] = index;
    25.           } else if (target > nums[index]) {
    26.               i = index + 1;
    27.           } else if (target < nums[index]) {
    28.               j = index;
    29.           }
    30.       }
    31.       return res;
    32.   }
    34.   //2.遍历版本2
    35.   public int[] searchRange(int[] nums, int target) {
    36.       int[] res = new int[]{-1, -1};
    37.       if (nums.length == 0) return res;
    38.       int i = 0, j = nums.length - 1, index = -1;
    39.       //左边界
    40.       while (i <= j) {
    41.           index = (i + j) / 2;
    42.           if (target == nums[index]) {
    43.               i = index + 1;
    44.               res[1] = index;
    45.           } else if (target > nums[index]) {
    46.               i = index + 1;
    47.           } else if (target < nums[index]) {
    48.               j = index - 1;
    49.           }
    50.       }
    51.       i = 0; j = nums.length - 1;
    52.       //右边界
    53.       while (i <= j) {
    54.           index = (i + j) / 2;
    55.           if (target == nums[index]) {
    56.               j = index - 1;
    57.               res[0] = index;
    58.           } else if (target > nums[index]) {
    59.               i = index + 1;
    60.           } else if (target < nums[index]) {
    61.               j = index - 1;
    62.           }
    63.       }
    64.       return res;
    65.   }
    67.   //3.递归版本
    68.   public int[] searchRange(int[] nums, int target) {
    69.       int leftIdx = binarySearch(nums, target, true);
    70.       int rightIdx = binarySearch(nums, target, false) - 1;
    71.       if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
    72.           return new int[]{leftIdx, rightIdx};
    73.       } 
    74.       return new int[]{-1, -1};
    75.   }
    77.   public int binarySearch(int[] nums, int target, boolean lower) {
    78.       int left = 0, right = nums.length - 1, ans = nums.length;
    79.       while (left <= right) {
    80.           int mid = (left + right) / 2;
    81.           if (nums[mid] > target || (lower && nums[mid] >= target)) {
    82.               right = mid - 1;
    83.               ans = mid;
    84.           } else {
    85.               left = mid + 1;
    86.           }
    87.       }
    88.       return ans;
    89.   }

    在排序数组中查找元素的第一个和最后一个位置