算法基础学习——二分查找（附带Java模板）

有单调性的数列一定可以使用二分，没有单调性的题目也可能可以使用二分；

（一）整数二分

二分的本质：

        在某个整数区间内，存在某种性质使得区间内左半边的数都不满足该性质；而右半边的数都满足该性质；那么二分的作用就是找到左右这两个分界点；

1.找满足红色性质的边界点（如图上）

如果是让l等于mid（即找左半边的分界点）则要记得mid = (l+r+1)/2

2.找满足绿色性质的边界点（如图上）

如果是让r等于mid（即找右半边的分界点）则mid = (l+r)/2，不用另外加1；

情况1为什么额外加1？ 答：因为在程序中，(l+r)/2是向下取整；当遇到遇到r=l+1（l和r只相差1，数组只有两个元素）的情况，(l+r)/2就等于l，这时候mid=(l+r)/2就是mid=l如下图所示：这次循环相当于没有变化，再次循环也不会有变化，进入死循环；

基本思想：不断缩小答案区间，当区间长度为一时，就是答案；

时间复杂度：平均O(logn) 

步骤：

1. 先写出基本模板:mid = (l+r)/2

2. 定义判断条件check()函数

3. 看应该是让l=mid还是r=mid；如果应该l=mid则把前面的mid改为 mid=(l+r+1)/2

模板：

// 检查x是否满足某种性质  
private static boolean check(int x) {  /* ... */  
}  // 区间[left, right]被划分成[left, mid]和[mid + 1, right]时使用： 
// 或者称之为左二分查询，查找左侧第一个满足条件的数
private static int leftBinarySearch(int[] arr, int left, int right) {  while (left < right) {  int mid = arr[left + right >> 1];  if (check(mid)) {  right = mid;    // check()判断mid是否满足性质  } else {  left = mid + 1;  }  }  return left;  
}  // 区间[left, right]被划分成[left, mid - 1]和[mid, right]时使用：  
// 或者称之为右二分查询，查找右侧最后一个满足条件的数
private static int rightBinarySearch(int[] arr, int left, int right) {  while (left < right) {  int mid = arr[left + right + 1 >> 1];  if (check(mid)) {  left = mid;    // check()判断mid是否满足性质  } else {  right = mid - 1;  // 有加必有减}  }  return left;  
}

（二）浮点数二分

典型问题：求一个数的平方根

基本思想：不断缩小答案区间，当区间长度足够小时（即左右边界之差足够小），边界的值就约等于答案；

时间复杂度：平均O(logn) 

步骤：

• mid就等于(r+l)/2;

• while循环判定条件为r-l>1e-8（左右边界之差足够小时结束循环）

模板：

// 检查x是否满足某种性质  
private static boolean check(int x) {  /* ... */  
}  // 区间[left, right]被划分成[left, mid]和[mid + 1, right]时使用： 
// 或者称之为左二分查询，查找左侧第一个满足条件的数
private static int leftBinarySearch(int[] arr, int left, int right) {  while (left < right) {  int mid = arr[left + right >> 1];  if (check(mid)) {  right = mid;    // check()判断mid是否满足性质  } else {  left = mid + 1;  }  }  return left;  
}  // 区间[left, right]被划分成[left, mid - 1]和[mid, right]时使用：  
// 或者称之为右二分查询，查找右侧最后一个满足条件的数
private static int rightBinarySearch(int[] arr, int left, int right) {  while (left < right) {  int mid = arr[left + right + 1 >> 1];  if (check(mid)) {  left = mid;    // check()判断mid是否满足性质  } else {  right = mid - 1;  // 有加必有减}  }  return left;  
}

注意点：

1. 使用二分一定可以找到一个满足条件的边界点（不会出现无解的情况）；

2. 整数二分中，l和r表示的是区间左右边界的数组下标；当遍历结束后l=r，arr[r] 就是所找的边界点；

3. 浮点数二分中，l和r表示的不是数组下标，而是左右边界本身；

时间复杂度分析

二分查找（Binary Search）的时间复杂度分析如下：

1. 最好情况（Best Case）

如果目标元素正好是数组的中间元素，那么只需一次比较就能找到，时间复杂度为：

O(1)O(1)

2. 最坏情况（Worst Case）

每次查找都会将搜索范围缩小一半，假设数组长度为 nn，那么最多需要查找的次数是：

T(n)=T(n/2)+O(1)T(n) = T(n/2) + O(1)

展开递归：

T(n)=T(n/4)+O(1)+O(1)=T(n/8)+O(1)+O(1)+O(1)=…T(n) = T(n/4) + O(1) + O(1) = T(n/8) + O(1) + O(1) + O(1) = \dots

直到搜索范围缩小到 1，即 n/2k=1n/2^k = 1，解得：

k=log⁡2nk = \log_2 n

因此，最坏情况下的时间复杂度是：

O(log⁡n)O(\log n)

3. 平均情况（Average Case）

在没有额外信息的情况下，平均情况下也需要进行大约 O(log⁡n) 级别的比较，因此平均时间复杂度也是：

O(log⁡n)

总结

情况	时间复杂度
最好情况	O(1)O(1)
最坏情况	O(log⁡n)O(\log n)
平均情况	O(log⁡n)O(\log n)

二分查找的时间复杂度远优于线性查找（O(n)），但前提是数据必须是有序的，否则需要先进行排序（如快速排序 O(nlog⁡n)），这会影响整体效率。