模板

  1. int binary_search(int[] nums, int target) {
  2.     int left = 0, right = nums.length - 1; 
  3.     while(left <= right) {
  4.         int mid = left + (right - left) / 2;
  5.         if (nums[mid] < target) {
  6.             left = mid + 1;
  7.         } else if (nums[mid] > target) {
  8.             right = mid - 1; 
  9.         } else if(nums[mid] == target) {
  10.             // 直接返回
  11.             return mid;
  12.         }
  13.     }
  14.     // 直接返回
  15.     return -1;
  16. }
  18. int left_bound(int[] nums, int target) {
  19.     int left = 0, right = nums.length - 1;
  20.     while (left <= right) {
  21.         int mid = left + (right - left) / 2;
  22.         if (nums[mid] < target) {
  23.             left = mid + 1;
  24.         } else if (nums[mid] > target) {
  25.             right = mid - 1;
  26.         } else if (nums[mid] == target) {
  27.             // 别返回，锁定左侧边界
  28.             right = mid - 1;
  29.         }
  30.     }
  31.     // 最后要检查 left 越界的情况
  32.     if (left >= nums.length || nums[left] != target)
  33.         return -1;
  34.     return left;
  35. }
  38. int right_bound(int[] nums, int target) {
  39.     int left = 0, right = nums.length - 1;
  40.     while (left <= right) {
  41.         int mid = left + (right - left) / 2;
  42.         if (nums[mid] < target) {
  43.             left = mid + 1;
  44.         } else if (nums[mid] > target) {
  45.             right = mid - 1;
  46.         } else if (nums[mid] == target) {
  47.             // 别返回，锁定右侧边界
  48.             left = mid + 1;
  49.         }
  50.     }
  51.     // 最后要检查 right 越界的情况
  52.     if (right < 0 || nums[right] != target)
  53.         return -1;
  54.     return right;
  55. }
  • 其中int mid = left + (right - left) / 2; 等价于(left + right) / 2，但防止了left + right过大产生溢出。
  • 以上是[left, right]搜索区间，right初始化为nums.length - 1，缩小范围时，left = mid +1 或 right = mid - 1; while的判断条件为left <= right，否则会漏掉一个。
  • 倘若是[left, right)搜索区间，right初始化为nums.length，缩小范围时，left = mid - 1 或 right = mid; while的判断条件是left < right，因为左闭右开，此时只夹着一个元素，等于的时候搜索区间就为空了。
  • 如果是搜索左右边界，则判断nums[mid] == target后，不直接返回，而是继续缩小搜索区间。当退出循环时，搜索下标越界或最终没找到（夹到的位置不是target）返回-1。

    例题

    34. Find First and Last Position of Element in Sorted Array

    1. class Solution {
    2.   public int[] searchRange(int[] nums, int target) {
    3.       if (nums == null || nums.length == 0) return new int[]{-1, -1};
    4.       int leftBound = 0, rightBound = 0;
    5.       // Find left bound
    6.       int left = 0, right = nums.length - 1;
    7.       while (left <= right) {
    8.           int mid = left + (right - left) / 2;
    9.           // 等于的时候，right继续向左缩小搜索范围
    10.           if (nums[mid] >= target) right = mid - 1;
    11.           else if (nums[mid] < target) left = mid + 1;
    12.       }
    13.       if (left > nums.length - 1 || nums[left] != target) return new int[]{-1, -1};
    14.       leftBound = left;
    15.       // Find right bound
    16.       left = 0;
    17.       right = nums.length - 1;
    18.       while (left <= right) {
    19.           int mid = left + (right - left) / 2;
    20.           if (nums[mid] <= target) left = mid + 1;
    21.           else if (nums[mid] > target) right = mid - 1;
    22.       }
    23.       if (right < 0 || nums[right] != target) return new int[]{-1, -1};
    24.       rightBound = right;
    25.       return new int[]{leftBound, rightBound};
    26.   }
    27. }
    基本就是按照上面的模板分别算出左右边界然后返回。