C++算法初级7——二分查找_c++二分查找

C++算法初级7——二分查找

二分查找的原理：每次排除掉一半答案，使可能的答案区间快速缩小。

二分查找的时间复杂度：O(log n)，因为每次询问会使可行区间的长度变为原来的一半。

我们再来看一下二分查找的思路：我们设定一个初始的L和R，保证答案在[L,R]中，当[L,R]中不止有一个数字的时候，取区间的中点M，询问这个中点和答案的关系，来判断答案是M，还是位于[L,M-1]中，还是位于[M+1,R]中。二分查找的伪代码如下：

int L = 区间左端点;
int R = 区间右端点; // 闭区间
while( L < R ) { // 区间内有至少两个数字
    int M = L+(R-L)/2; // 区间中点
    if( M是答案 ) 答对啦;
    else if( M比答案小 ) L = M+1;
    else R = M-1; // M比答案大
}
// 若运行到这里，因为答案一定存在，所以一定有L==R，且L是答案
1
2
3
4
5
6
7
8
9

在升序的数组上进行二分查找

在一个排好序的数组上二分查找一个数字x，一般都可以变成如下的问题：在数组中找到第一个大于等于x的数字的位置（假设数组是从小到大排好序的）。

问题： 输入n，x，以及一个长度为n的数组a（已经从小到大排好序了）

输出数组a中最左边的大于等于x的数字的下标，数组下标从0开始

输入数字都是1000000000以内的非负整数。数组长度不超过50000。若数组中不存在大于等于x的数字，输出-1

一些特殊情况:
请手动模拟一下这段代码在下面数组上的运行过程，体会一下这段代码是如何处理一些边界情况的。

比如：答案不存在的情况我们是如何处理的？

比如：当区间内只有两个数字的时候，这段代码还能正常运行吗？

比如：数组中有很多个重复元素的时候，这段代码还能正常运行吗？

比如：为什么循环结束之后一定有L == R？为什么不会出现L > R的情况？

请自己写一些简单情况出来，并手动模拟运行这段代码，想一想为什么这段代码不会出错。

比如：在2 3这个数组中找到第一个大于等于3的元素。

比如：在2 3 3 3 3 4 4 4 4这个数组中找到第一个大于等于4的元素。

倒过来怎么做
那现在，如果你面临一个新的问题：

有一个从小到大排好序的数组，你要找到从右向左数第一个小于等于x的数字，应该怎么做？
问题：输入n，x，以及一个长度为n的数组a（已经从小到大排好序了）

输入样例：

9 4

2 3 3 3 3 4 4 4 4

我们可以把问题转化为“找到从左往右数最后一个小于等于x的数字”，这时候就可以写出L = 0, R = n-1这样的初始条件。

有些复杂的问题，进行问题转换也是较为困难的，因此我们需要总结出一个不费脑子、不需要思考就可以写出优美代码的做法。

我们注意到，二分查找的精髓在于，只通过a[M]的值来判断：答案是在左半边还是在右半边。

因此，我们只要抛弃传统意义上的“大小”概念，牢牢抓住这一点进行分析，仔细推断出这个条件用到的表达式，就一定可以写出优美的代码。

糟糕！死循环！
但是！假设现在有L = 3, R = 4，你要找的是最后一个小于等于x = 100的数字，并且数组元素是a[3] = 80, a[4] = 90。

然后通过计算得到中点M = 3，检查发现a[3] <= 100，所以执行L = M，把答案的可行区间变成[M,R]。

你已经发现问题了！在经过一次二分之后，变量仍然保持了L = 3, R = 4没有变化，循环条件L < R一直被满足，我们始终无法结束循环。

这就让我们的程序进入了死循环！

为什么会死循环？

如果你实现了刚刚问题（有一个从小到大排好序的数组，你需要找到从左往右数最后一个小于等于x的数字）的代码，你可能会写出下面这样的代码。

int L = 0, R = n-1;
while( L < R ) {
    int M = L + (R - L)/2;
    if( a[M] <= x ) { // 答案一定在[M,R]中
        L = M;
    } else { // 答案一定在[L,M - 1]中
        R = M - 1;
    }
}
// a[L]就是答案
1
2
3
4
5
6
7
8
9
10

但是你发现，这个程序好像存在一些问题：有时候，程序会陷入死循环，无法得到运行结果。这是为什么呢？

和最初的问题对比一下，你能发现这两份代码的不同之处吗：

// 最初的问题：在数组中找到从左往右 第一个 大于等于x的数字的位置
if( 答案在[M + 1,R]中 ) {
    L = M + 1;
} else {
    R = M; // 这里可能引发“差一点”问题
}
// 现在的问题：在数组中找到从左往右数 最后一个 小于等于x的数字
if( 答案在[M, R]中 ) {
    L = M;
} else {
    R = M - 1
}
1
2
3
4
5
6
7
8
9
10
11
12

这段代码在逻辑上肯定是没有错误的 —— 你每次都把正确的区间挑选出来了。那为什么这段代码会在某些时候引起死循环呢？

如何避免问题?
事实上，死循环只会在刚刚这种况出现：

假设现在有L = 3, R = 4，你要找的是最后一个小于等于x = 100的数字，并且数组元素是a[3] = 80, a[4] = 90。

然后通过计算得到中点M = 3，检查发现a[3] <= 100，所以执行L = M，把答案的可行区间变成[M, R]。

在经过一次二分之后，变量仍然保持了L = 3, R = 4没有变化，循环条件L < R一直被满足，我们始终无法结束循环。

这是因为我们在判断出答案在[M, R]中的时候，执行了L = M这句话，而根据我们的中点计算公式M = L + (R - L)/2，我们在R == L+1的情况下总会得到L == M。所以我们在经过一次二分之后，L和R的值没有发生变化，也就陷入了死循环。

要避免这个问题，其实也非常简单，我们只需要把中点计算公式变成M = L + (R - L + 1)/2即可。在之前的中点计算公式M = L + (R - L)/2中，我们如果遇到了中点不是整数的情况，则会把中点向下取整，因此在出现L + 1 == R这种情况的时候就会始终有L == M从而引发问题。现在我们通过一个+1使得在中点不是整数的时候把中点向上取整，就可以避免这个问题（请在纸上模拟代码的运行过程，以体会这个公式是如何解决“差一点”问题的）。

总结

正如之前说的，二分查找中其实还有很多细节问题没有处理，比如：

• 如果循环最后因为不满足L < R条件而退出，这时候L和R到底是什么关系？答案是什么？
• 如果答案不存在会怎么样？

应用范围

如果我们想要在一个数组上进行二分查找，那么这个数组必须是有序的，不管是升序还是降序，它必须是有序的。为什么呢？

注意二分查找的本质是什么：通过比较数组中间那个值和我们要求的值的关系，来判断出“答案不可能出现在数组的某一半”，从而让我们的查找范围缩小为原来的一半。

这也就是为什么我们要求数组中的元素是满足单调性的：只有这样，我们才能保证当a[M]不满足条件的时候，它左边（或者右边）的所有元素都不满足条件。

那么是不是任何有序的数据结构都可以应用二分查找算法呢？

日期

日期是一个天然有序的结构：我们可以定义日期A小于日期B意为：在日历上A排在B的前面。比较两个日期的大小也可以通过很简单的方式进行：先比较年，再比较月，最后比较日。

struct Date {
    int year, month, day;
};
bool operator<( const Date &a, const Date &b ) {
    if( a.year == b.year ) {
        if( a.month == b.month ) {
            return a.day < b.day;
        } else {
            return a.month < b.month;
        }
    } else {
        return a.year < b.year;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

但是我们可能会面临一个问题：如果我们要在公元1年1月1日和1000000000年1月1日之间二分，我们该如何求出两个日期的中点呢？

我们把日期表示成YYYYMMDD的形式，比如公元1年1月1日就是00010101，1000000000年1月1日就是10000000000101。则两个日期的中点，就是两个数字的中点，只不过我们需要把这个数字向下取整（或者向上取整）到最近的合法的日期。

比如，我们要求19701212和20200817的中点，我们可以直接求(19701212 + 20200827) / 2 = 19951019，这就是这两个日期的近似中点。如果我们得到了类似于19971805这样不合法的日期（没有18月），我们只需要把18月向下取整到合法的日期（12月），变为19971205即可。

字符串

字符串也是一个天然有序的数据结构：字典序就是字符串的大小顺序。因此我们可以给一堆字符串按照字典序排序。

string s[100];
for( int i = 0; i < n; ++i )
    cin >> s[i];
// sort函数用于给数组中的元素排序
sort(s, s+n); // string类的比较函数为比较两个字符串的字典序
1
2
3
4
5

现在在一堆排好序的字符串中，我们要找出所有前缀是com的字符串，应该怎么做呢？
容易发现，所有前缀是com的字符串，在数组中也是一个连续的区间。

我们可以把数组中的所有字符串截断到前3位，然后使用二分查找法找到第一个com出现的位置和最后一个com出现的位置。

在这之间的所有字符串，前缀都是com。

有的时候我们需要用到二维数据，比如平面中的点，就需要两个数字来表示，再比如std::pair这个数据结构，就是简单地把两个数字组合在一起。

不妨假设我们遇到的二维数据都是下面这样子的。类似平面上的整数点，一个点用两个整数(x,y)表示。

struct Point {
    int x, y;
};
// 这是运算符重载，当我们在代码中用小于号比较两个Point类变量的时候，就会用这个函数进行比较
bool operator<( const Point &a, const Point &b ) { // 如何定义a < b
    if( a.x == b.x ) {
        return a.y < b.y;
    } else {
        return a.x < b.x;
    }
}
1
2
3
4
5
6
7
8
9
10
11

这里我们定义了一种常用的比较二维数据的方法：首先比较两个数据的第一维，数字小的排在前面，当第一维数字相同的时候，比较第二维，数字小的排在前面。比如(3,3) < (4,2)，因为先比较第一维3 < 4。再比如(2,3) < (2,5)，因为第一维相同时比较第二维。

如果我们有一个排好序的Point数组，我们想找到数组中所有x = 5的元素（容易发现所有x = 5的元素在数组中一定是一个连续的区间），应该怎么做呢？

一个排好序的Point数组例子：(1,2), (2,3), (2,4), (5,-1), (5,2), (5,5), (7,4)。

Point a[100000];
for( int i = 0; i < n; ++i )
cin >> a[i].x >> a[i].y;
sort(a, a+n); // sort函数可以给数组中的元素排序

我们只需要两次二分查找就可以了：分别找到第一个大于等于Point(5, INT_MIN)的元素，以及最后一个小于等于Point(5, INT_MAX)的元素。这两个元素中间的所有元素就是x = 5的所有元素（闭区间）。INT_MIN和INT_MAX分别是int所能表达的最小值和最大值。

应用

我们总结一些二分查找的常见应用：

1. lower_bound和upper_bound

lower_bound的用途是：在指定的升序排序的数组中，找到第一个大于等于x的数字。

upper_bound的用途是：在指定的升序排序的数组中，找到第一个大于x的数字。

使用lower_bound和upper_bound可以帮我们解决绝大多数二分查找问题。

这两个函数会返回对应数字的指针。示例代码如下：

int a[100000], n;
cin >> n;
for( int i = 0; i < n; ++i )
    cin >> a[i];
sort(a, a + n);
int *p = lower_bound(a, a + n, 13); // 第一个大于等于13的数字
int *q = upper_bound(a, a + n, 13); // 第一个大于13的数字
1
2
3
4
5
6
7

假如我们使用lower_bound和upper_bound二分查找同一个数字13，容易发现，我们得到的两个指针构成了一个左闭右开区间，这个区间里全部都是数字13。

巧妙地运用这两个函数，可以完成所有常见的二分查找操作：

• 找到第一个大于等于x的数字
• 找到第一个大于x的数字
• 找到最后一个等于x的数字
• 查找数组中是否有数字x
• 查询数组中有几个数字x
• 找到最后一个小于x的数字

2. 二分法可以求方程的近似解。

3. 二分法可以用来优美地实现离散化操作。

4. 在double上二分时，尽量使用固定次数二分的方法。

求方程的解
问题

请输出方程x^3 + 16 = 0的解，已知这个解在[-1e9,1e9]之间，并且函数f(x) = x^3 + 16在定义域上单调递增。输出的答案保留5位小数。

我们现在想求出某个方程f(x) = 0的解，并且我们知道这个解在[L,R]之间，且函数f(x)在[L,R]上单调递增。我们只需要这个解精确到5位小数即可。


在double上二分的注意事项

你可能会发现，最终的结果并没有精确到10位小数，或者是这个二分直接陷入了死循环。

在精度要求越高的时候，就越可能出现这样匪夷所思的情况。

这是因为double本身存在不小的精度误差，我们通过R - L >= 1e-10这种方式来控制二分的终止条件，会带来非常大的精度问题。

这种时候，我们可以采用固定次数二分的方法：

double L = -1e9, R = 1e9;
for( int times = 0; times < 100; ++times ) { // 二分100次
    double mid = (L+R)/2;
    // 此处省略二分内容
}
1
2
3
4
5

这里我们二分100次，是因为2的100次方约为1e30，而我们二分的初始条件是1e9左右，足以在最后把精度控制在1e-20左右。

在这种二分策略下，我们一般都能得到合理的答案。