本文转载，侵告立删
几个最常用的二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。

1. 正常的二分搜索(寻找一个数）

  1. int binarySearch(int[] nums, int target) {
  2.     int left = 0; 
  3.     int right = nums.length - 1; // 注意
  5.     while(left <= right) {
  6.         int mid = left + (right - left) / 2;
  7.         if(nums[mid] == target)
  8.             return mid; 
  9.         else if (nums[mid] < target)
  10.             left = mid + 1; // 注意
  11.         else if (nums[mid] > target)
  12.             right = mid - 1; // 注意
  13.     }
  14.     return -1;
  15. }
  1. 注意区间是左闭闭开[l,r]，则right=n-1,while(l<=r);还是左闭右开[l,r),则right=n,while(l<r）?
  • 左闭右闭时，while(l<=r)循环的中止条件时left > right,即搜索到区间[right+1,right],此时返回-1。
  • 左闭右开时，while(l<r)循环的中止条件时left == right,即搜索到区间[right,right)。需要加上 return nums[left] == target ? left : -1;
  1. 为什么left = mid + 1，right = mid - 1？我看有的代码是right = mid或者left = mid，没有这些加加减减，到底怎么回事，怎么判断？

刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即[left, right]。那么当我们发现索引mid不是要找的target时，下一步应该去搜索哪里呢？当然是去搜索[left, mid-1]或者[mid+1, right]对不对？因为mid已经搜索过，应该从搜索区间中去除。
总结：在搜索一个target时，用闭区间且l<=r的形式。

2 二分搜索target的左边界

搜索target的左边界的意思是寻找第一个等于target的元素，不断收缩右边界。

  1. int left_bound(int[] nums, int target) {
  2.     if (nums.length == 0) return -1;
  3.     int left = 0;
  4.     int right = nums.length; // 注意
  6.     while (left < right) { // 注意
  7.         int mid = (left + right) / 2;
  8.         if (nums[mid] == target) {
  9.             right = mid;
  10.         } else if (nums[mid] < target) {
  11.             left = mid + 1;
  12.         } else if (nums[mid] > target) {
  13.             right = mid; // 注意
  14.         }
  15.     }
  16.     return left;
  17.     /*
  18.     // target 比所有数都大
  19.         if (left == nums.length) return -1;
  20.         // 类似之前算法的处理方式
  21.         return nums[left] == target ? left : -1;
  22.     */
  23. }
  1. 注意这里是**r=n,l<r**，是最常见的写法记住即可。
  2. 为什么left = mid + 1，right = mid？和之前的算法不一样？

答：这个很好解释，因为我们的「搜索区间」是[left, right)左闭右开，所以当nums[mid]被检测之后，下一步的搜索区间应该去掉mid分割成两个区间，即[left, mid)或[mid + 1, right)。

  1. 当target==num[mid]时 需要缩小查找上界，即不断向左收缩，达到锁定左侧边界的目的。right = mid;
  2. 如果是使用r=n-1,l<=r的情况是什么？
  • while循环的中止条件是l=r+1,[r+1,r]此时可能会有target比所有元素都大而导致left索引越界。需要加个判断：

**if** (left >= nums.length || nums[left] != target)<br /> **return** -1;<br />** return** left;

  • 搜搜区间的更新是与第一种搜索类似，只不过当num[mid]==target时，要收缩右边界right==mid-1;

  1. 当左边界意味着寻找最后一个小于target的元素（一个<taget的最大元素），即最靠近target的左侧元素。其算法变形在于**return left-1**。即可

    3 二分搜索target的右边界

    搜索target的右边界的意思是寻找最后一个等于taget元素。

    1. int right_bound(int[] nums, int target) {
    2.  if (nums.length == 0) return -1;
    3.  int left = 0, right = nums.length;
    5.  while (left < right) {
    6.      int mid = (left + right) / 2;
    7.      if (nums[mid] == target) {
    8.          left = mid + 1; // 注意
    9.      } else if (nums[mid] < target) {
    10.          left = mid + 1;
    11.      } else if (nums[mid] > target) {
    12.          right = mid;
    13.      }
    14.  }
    15.  return left - 1; // 注意
    16.  /*
    17.  if (left == 0) return -1;
    18. return nums[left-1] == target ? (left-1) : -1;*/
    19. }

  2. 其实对于左闭右开区间的边界寻找大部分代码是一样的，只有在nums[mid] == target时有区别：

  • 当寻找左边界时， if (nums[mid] == target) {不断缩小右边界来缩小范围 r=mid}。

所以在极端下（target比所有都大）可能无法缩小查找范围，只能不断移动左指针导致l==num.size();

  • 当寻找左边界时， if (nums[mid] == target) {不断扩大左边界来缩小范围 l=mid+1}。
  • 所以在极端下（target比所有都小）可能无法缩小查找范围，只能不断移动右指针导致r=l=0。
  1. 这个当num[mid]==target时，需要增大left下界来找到第一个大于taget的元素。
  2. 为什么返回left-1?

因为我们对left的更新必须是left = mid + 1，就是说 while 循环结束时，nums[left]一定不等于target了，而nums[left-1]可能是target。
3.当寻找的一个大于target的最小元素时，返回left即可。
4.当没有找到时，即所有元素都小于target,那么left=right=n,返回-1。

if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;