二分查找

前言： 二分查找虽然并不是什么很难的东西， 但因为我始终背不下来， 每次要用的时候都得现场小心翼翼地推导细节， 十分苦恼。因此希望通过写一篇笔记总结， 把它刻入我的记忆。

基本概念

不再赘述， 引用维基百科： > 在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）[1]、对数搜索算法（英语：logarithmic search algorithm）[2]，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找的框架

二分查找的步骤大概是： * 定义二分查找的左右边界 * 循环体， 循环条件一般为左边界不大于右边界 * 取中值（准确说是左右边界的平均值， 即中间元素） * 用中值与查找的目标元素比较， 从而移动左右边界

二分查找的三种应用形式

通过对取中值以及对左右边界移动的细节处理， 可以得到不同功能的二分查找。

最朴素的二分查找

最朴素的二分查找的用法是： 查找某值是否在数组中出现过， 是则返回下标， 否则返回-1.

int binarySearch(vector<int> &nums, int l, int r, int target) {
    while(l < r) {
        int mid = (l + r) >> 1;
        if(nums[mid] == target) {
            return mid;
        } else if(nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return -1;
}

### 查找左边界 / 第一个大于等于target的元素

在朴素二分中， 若数组中有多个值为target的元素， 返回的下标对于使用者而言是合理情况中的随机一个；若数组中中没有值为target的元素， 返回值将是无意义的-1.

接下来两种二分便是为了解决这一类问题。

在左边界二分中， 要查找的元素e满足：e左边的元素都小于target, e右边的元素及e都不小于（大于等于）target.

int binarySearch_lower(vector<int> &nums, int l, int r, int target) {
    while(l < r) {
        int mid = (l + r) >> 1;
        if(nums[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

查找右边界 / 第一个小于等于target的元素

类似的， 在左边界二分中， 要查找的元素e满足：e右边的元素都大于target, e右边的元素及e都不大于（小于等于）target.

int binarySearch(vector<int> &nums, int l, int r, int target) {
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(nums[mid]  <= target) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

### 细节1——取中值时的左偏和右偏

当[l, r]中有奇数个元素时如[1, 2, 3]， 中值显然为中间那个元素。 但当[l, r]中有偶数个元素时如[1, 2, 3, 4]， 中值到底是2还是3呢？

这就取决于mid的取法了

mid = (l + r) >> 1;
mid = (l + r + 1) >> 1; 

c++的中整数除法是与右移一位的效果完全相同的， 即整除， 当[l, r]中有偶数个元素时, 显然l + r为奇数， 所以(l + r) >> 1结果会偏向l这一边 而相反的(l + r + 1) >> 1会偏向r这一边。

取中的偏向是相当重要的问题， 若使用错误， 二分可能将陷入死循环。

在结论上， 可以简单的记忆为左边界左偏， 右边界右偏

细节2——左右边界的更新方式

边界二分与朴素二分很大的一个区别是： 朴素二分靠mid查找目标值， 若nums[mid] == target就立即返回； 而边界二分是靠不断缩小查找的区间， 最终区间长度为1时(l == r)， 区间中唯一的元素即为目标值。 以左边界二分举例

while(l < r) {
  int mid = (l + r) >> 1;
  if(nums[mid] >= target) {
  	r = mid;
  } else {
  	l = mid + 1;
  }
}

要找的是左边界， 当nums[mid] > target时， 是不能将r置为mid - 1的， 因为也许mid就是左边界； 类似的， 当nums[mid] == target时， 你不能确定mid左边是否是左边界， 但mid + 1往后的元素你可以确定一定不是左边界， 因此将r赋为mid， 缩小范围， 继续查找。 而只有当nums[mid] < target时， 才移动l， 此时mid显然不是左边界， 所以将l赋为mid + 1

补充1——取中值时的溢出

在区间较大情况下， 使用(l + r)直接取中值时可能会溢出整型范围。 所以可以用如下方式等价取代

mid = l + ((r - l) >> 1);
mid = l + ((r - l + 1) >> 1);

补充2——查找失败

若要找第一个不小于target的元素， 但数组中所有元素都小于target? 此时l会不断向右移动， 直到移到到r的位置。 所以查找结束后， 可以在对结果进行一次判断， 如果不满足就返回-1.

int binarySearch(vector<int> &nums, int l, int r, int target) {
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(nums[mid]  <= target) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return nums[l] <= target ? l : -1;
}

## 二分查找的应用

二分查找最常见的应用就是在数组中查找某个值的左边界或右边界， 但还有一种的用法是浮点数二分， 必如求一个浮点数的n次方根。

给定一个浮点数 nn，求它的三次方根。

输入格式

共一行，包含一个浮点数 nn。

输出格式

共一行，包含一个浮点数，表示问题的解。

注意，结果保留 66 位小数。

数据范围

−10000≤n≤10000−10000≤n≤10000

输入样例：

1000.00

输出样例：

10.000000

思路 用二分的思想不断更新左右边界， 使左右边界逐渐逼近答案， 当左右边界足够接近答案时（达到精度要求）， 即认为左/右边界就是答案。 参考代码

# include <bits/stdc++.h>
using namespace std;

int main() {
    double n; cin >> n;
    double l = -100, r = 100;
    while((r - l) > 1e-8) {
        double mid = (l + r) / 2;
        if(mid * mid * mid > n) {
            r = mid;
        } else {
            l = mid;
        }
    }
    printf("%.6lf\n", l);
    return 0;
}

参考

二分 - OI Wiki (oi-wiki.org)

二分查找算法 - 维基百科，自由的百科全书 (wikipedia.org)

二分查找、二分边界查找算法的模板代码总结 - SegmentFault 思否