二分查找是计算机科学中最基本、最有用的算法之一，在基础算法的学习中是非常重要的。
二分查找的最基本问题是在有序数组里查找一个特定的元素（「力扣」第 704 题：二分查找）。
IMG20211118100010.png

二分查找虽然思想很简单，但事实上很多时候编码【边界的细节处理是魔鬼】很容易出错。

通常情况下，只要给定的一个问题的答案解满足【二段性】那么我们就可以考虑是否可以二分。

二段性

  • 例如集合中的元素有存在分界线，给定某一个条件可以将集合中元素分为两部分，一部分满足条件，一部分不满足条件。
  • 或者一段时间内某一个时刻满足题目的解，不妨设为 t ，此时 大于等于 t 的都满足 小于等于 t 的都不满足条件

在二分查找中，也存在分界线，分界线以前的元素满足某个条件，分界线以后的元素不满足该条件。我们每一轮搜索就是要确定一个分界线。从而我们每次就可以利用【分冶的思想】减少搜索的区间范围

二分查找的时间复杂度为 算法-【二分查找】 - 图2

举个例子 上面的二分查找某个target元素 先贴出AC代码

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         // 定义搜索的下界 和上届
  4.         int left = 0,right = nums.length -1;
  5.         // 结束搜索的条件
  6.         while(left < right){
  7.             // 每次选择一个中间的数字
  8.             int mid = (left + right) >>> 1;
  9.             // 符合条件直接返回
  10.             if(nums[mid] == target){
  11.                 return mid;
  12.             }
  13.             // 判断条件 这里就是二段性的表现，nums[mid] < target 那么意味着 [0,mid] 区间的数都小于targer
  14.             // 可以确定下一轮搜索范围为 [mid+1,right] 
  15.             if(nums[mid] < target){
  16.                 left = mid + 1;
  17.             }else{
  18.                 // 这里代表[mid,right] 整个区间数都大于 target 所以我们将下一轮搜索范围改为 [left,mid] 即 right = mid
  19.                 right = mid;
  20.             }
  21.         }
  22.         // 结束时有 left == right 成立
  23.         // 视情况，是否需要单独判断 left（或者 right）这个下标的元素是否符合题意
  24.         return nums[left] == target ? left:-1;
  26.     }
  27. }

上面我们每次选择中间数字的时候采用的是 (left + right) >>> 1; 这样写是没问题的。但是如果直接写成
（left+right）/ 2 是有问题的，因为这样可能溢出int最大值。还有一种写法是left+(right-left)/2。

二分模板

模板一

选择中位数的时候下取整

  1. public int search(int[] nums, int left, int right, int target) {
  2.     while (left < right) {
  3.         // 选择中位数时下取整
  4.         int mid = left + (right - left) / 2;
  5.         if (check(mid)) {
  6.             // 下一轮搜索区间是 [mid + 1, right]
  7.             left = mid + 1
  8.         } else {
  9.             // 下一轮搜索区间是 [left, mid]
  10.             right = mid
  11.         }
  12.     }
  13.     // 退出循环的时候，程序只剩下一个元素没有看到。
  14.     // 视情况，是否需要单独判断 left（或者 right）这个下标的元素是否符合题意
  15. }

选择中位数的时候上取整

  1. public int search(int[] nums, int left, int right, int target) {
  2.     while (left < right) {
  3.         // 选择中位数时上取整
  4.         int mid = left + (right - left + 1) / 2;
  5.         if (check(mid)) {
  6.             // 下一轮搜索区间是 [left, mid - 1]
  7.             right = mid - 1;
  8.         } else {
  9.             // 下一轮搜索区间是 [mid, right]
  10.             left = mid;
  11.         }
  12.     }
  13.     // 退出循环的时候，程序只剩下一个元素没有看到。
  14.     // 视情况，是否需要单独判断 left（或者 right）这个下标的元素是否符合题意
  15. }

模板二

  1. class Solution {
  3.     public int search(int[] nums, int target) {
  4.         // 特殊用例判断
  5.         int len = nums.length;
  6.         if (len == 0) {
  7.             return -1;
  8.         }
  9.         // 在 [left, right] 区间里查找 target
  10.         int left = 0;
  11.         int right = len - 1;
  12.         while (left <= right) {
  13.             // 为了防止 left + right 整形溢出，写成如下形式
  14.             int mid = left + (right - left) / 2;
  16.             if (nums[mid] == target) {
  17.                 return mid;
  18.             } else if (nums[mid] > target) {
  19.                 // 下一轮搜索区间：[left, mid - 1]
  20.                 right = mid - 1;
  21.             } else {
  22.                 // 此时：nums[mid] < target
  23.                 // 下一轮搜索区间：[mid + 1, right]
  24.                 left = mid + 1;
  25.             }
  26.         }
  27.         return -1;
  28.     }
  29. }

注意事项

二分的模板非常多，不同的模板写法退出循环的边界条件，以及确定下一轮二分搜索的范围处理方式都不一样。细节非常多。

  • 结束搜索的条件是 left < right 还是 left <= right
  • 确定中间数字的时候是上取整 还是 下取整 (left+right) >>> 1 或者 上取整 left + (right - left + 1) / 2
  • 下一轮搜索的边界怎么确定。left = mid + 1 还是 left = mid right = mid 还是 right = mid-1
  • 退出搜索后，left是否等于 right? 或者需不需要再对 left 和 right 做特殊判定

建议不要死背模板，要自己去理解，多去调试几个例子跑一下，先写出大体的框架，再去考虑是否需要上取整，以及确定边界。