二分查找的三种写法和四个目标

三种写法

二分查找经常碰到的问题就是写成了一个死循环。产生这个问题的根本原因是没有搞清楚二分查找左右两个边界到底应该怎么定义。

其实两个边界怎样定义都可以，但要一以贯之，这样就不会错。如果进行了混用则就会导致死循环。

下面列举3种二分查找的写法，用任何一种都可以，但切记别混了。

闭区间

闭区间指的是左边L和右边R这两个边界上的值是不确定的，在这个区间[L,R]外面的数都是已经确定了不满足的。

在闭区间的情况下：

• 初始化时L=0，R=n-1 刚好表示完整数组

• 如果mid处小于target，要将L更新为mid+1，因为已经明确了mid和之前的数都不要

• 如果mid处大于target，要将R更新为mid-1，同样因为已经明确了mid和之后的数都不要

• 循环条件是L<=R，会发现跳出的时候，R已经跑到L前面一位了, L就是最终的答案

public int lower_bound(int[] nums, int target){
  int l = 0;
  int r = nums.length-1;
  while(l<=r){
    int mid = l + (r-l)/2; //很重要，防止溢出
    if(nums[mid]<target){
      l = mid+1;
    }else{
      r = mid-1;
    }
  }
  return l;
}

左闭右开

左闭右开或者左开右闭是类似的，这里用左闭右开来说明。左闭右开，说明左闭L是第一个不确定的数，比L小的一定不行。右开，说明右边R是第一个不行的数，R以及R右边的都不行

因此：

• 初始化L=0,R=n R直接就是越界的，肯定不满足

• 如果mid比target小，则L=mid+1，保证L是第一个不确定的，mid已经证明肯定不行

• 如果mid比target大，则R=mid，mid以及右边的都不行，按照开区间的定义，此时R=mid

• 循环条件，L<R，最终L和R会相等，就是答案

public int lower_bound(int[] nums, int target){
  int l = 0;
  int r = nums.length; //右开
  while(l<r){
    int mid = l + (r-l)/2; //很重要，防止溢出
    if(nums[mid]<target){
      l = mid+1;
    }else{
      r = mid;
    }
  }
  return l;
}

开区间

最后讲一下开区间的写法，按照定义，开区间L和R都代表这不满足条件的数，L+1和R-1则表示待定的部分。

因此：

• 初始化L=-1, R=n

• 如果mid小于target，则mid和其左侧都不行，所以L=mid

• 如果mid大于target，则mid和其右侧都不行，所以R=mid

• 循环条件为L+1<R，即这个开区间内至少要有数字才继续验证，最终R指向答案

public int lower_bound(int[] nums, int target){
  int l = -1;
  int r = nums.length-1;
  while(l+1<r){
    int mid = l + (r-l)/2; //很重要，防止溢出
    if(nums[mid]<target){
      l = mid;
    }else{
      r = mid;
    }
  }
  return r;
}

四种目标

讲完了三种写法，你是否好奇，我们找的到底是谁？是target吗？是的但不全是。我们讨论如下几种情况：

• 如果数组中有多个target，会返回哪一个呢？答案是会返回第一个

• 如果数组中没有target，会返回哪一个呢？答案是会返回第一个大于target的数

• 如果数组中全部小于target，会返回哪一个呢？答案是会返回数组的长度，l推到越界的位置

因此，上面二分写法之所以命名为lower_bound，是因为其准确定义是，找到有序数组中第一个大于等于target的数字。

那么新的问题来了：

• 如果我想找到第一个大于target的数字应该怎么做呢？

  • 这其实等效于找到第一个大于等于target+1的数字（数组内都是整数）

  • 即 lower_bound(nums, target+1)

• 如果我想找到最后一个小于target的数字呢（换句说法，最接近target但小于target）？

  • 这其实等效于我先找到第一个大于等于target的数字，那这个数字左边的数字（-1）一定是最后一个小于target的

  • 即 lower_bound(nums, target)-1

• 如果我想找到最后一个小于等于target的数字呢？

  • 这其实等效于我先找到大于target的第一个数，这个数左边的数，就是最后一个小于等于target的数字。

  • 即 lower_bound(nums, target+1)-1

总结

三种写法完全等效，但推荐开区间写法，因为比较简单，少写几个字符。

一定注意防止溢出（面对任何先增大再减小的情况，都可以用先减再加来防止溢出）

通过对目标值的灵活运用，二分法不只可以帮我们找到等于target的结果，更可以帮我们找到

• 第一个大于target

• 最后一个小于target

• 第一个大于等于target

• 最后一个小于等于target