2023年秋季课第 4 课（ 二分查找 ）

1. 二分查找算法的意义

二分查找这个算法是用来提升数据的检索效率的。假定我们有一个有序的数组 {1,2,5,9,21,35,36,40,41,42,50,53,55,61,65,72,73,75,80,85,87,89}，然后有人问你，这个数组里面存在数字 40 吗？按照我们过去的认知，我们就是弄一个 for 循环，遍历每一个数组元素，然后用数组元素和 40 比较。代码大致上是这样的。

int a[22]={1,2,5,9,21,35,36,40,41,42,50,53,55,61,65,72,73,75,80,85,87,89};
bool Found=false;
for(int i=0;i<22;i++)
    if(a[i]==40)
    {
        Found = true;
        break;
    }
if(Found) cout<<"找到了 40";
else cout<<"没有找到 40";

上面这段代码很容易理解，没什么技术含量，关键是效率很低。假设这个数组有 $10^5$ 个数字，然后，你要查 $10^5$ 个数是否在数组里存在，那么计算复杂度就是 O($10^{10}$)，这一定要超时的。所以，我们今天学的算法意义很明确：二分查找就是提升数组查找的效率的。

2. 二分查找算法是什么

二分查找也叫折半查找，这个算法存在的前提条件是数组里的数是有序排列的，要么从小到大排序，要么从大到小排序。

我要在 {1,2,5,9,21,35,36,40,41,42,50,53,55,61,65,72,73,75,80,85,87,89} 中找数字 40，那么就先看看这个数列中间的那个数是什么。

1. 中间的数是 50 ，50 比 40 大，所以，40 只会存在于 50 之前的那一半数字当中，因此，问题变成了在 {1,2,5,9,21,35,36,40,41,42} 中找 40

2. 为了在 {1,2,5,9,21,35,36,40,41,42} 中找 40，我们拿出中间的数字，是 21 （你说是 21 也行，说是 35 也行，差别不大），21 比 40 小。所以，40 只可能存在于后半段，也就是 {35,36,40,41,42}

3. {35,36,40,41,42} 中找 40 ，我们拿出了中间的数字，刚好是 40 ，我们找到了

在这个例子中，我们其实不断收缩查找的范围，一开始是 [1,n], 然后是 [1,n/2] ，然后是[n*3/4,n/2]......每次收缩，都大致是收缩了一半的范围。

所以，如果数组里有 $10^5$ 个数，我们通过 15 次范围搜索，就能收缩到不能在收缩（因为 $2^{16}$ > $10^5$ ）,不能搜索，意味着 [l,r] 这个区间就剩下 2 个数，l 和 r 之间没有别的数字了。那我们自然就知道 最终找得到还是找不到了。

所以，意味着用这个方法，最多找不到 20 遍，就可以在 $10^5$ 个数字里头找到你要找的数字，你说是不是很神奇？

3. 左边界查找和右边界查找

如果问的问题稍稍改一下，改成：让你在有序数列中找到某个数字第一次出现的位置，这叫左边界查询；如果让你在有序数列中某个数字最后一次出现的位置，这叫右边界查找。

这两个问题其实还是折半查找问题，还是用数列中间位置的数和要找的数对比，根据不同的对比结果进行范围收缩。比较结果和收缩的方法是有强对应关系的，大家自己自己琢磨

4. 何时结束折半查找的逻辑

折半查找就是每次缩小一般区域，这是一个 while 语句。总要在某个时候退出循环，否则就是死循环了。退出循环有几个情况

1. 等于查找(数列中数字都不一样），a[mid]==x 了，就是找到了，可以退出

2. 当 low==high 的时候，也就是说，剩余的搜索区域就剩下 1 个数（a[low] 就是 a[high] ，一个数），这时候退出循环。再检查一下 a[low] 和 a[high] 就可以得到最终答案。

3. 在模板题的介绍中，我们说到过可能 high 跑到了 low 的前面（low>high），以这种方式退出循环的，也说明了是找不到符合要求的内容。假设数组是用到 a[1] ~ a[n] ，那么 a[0] 和 a[n+1] 就是两个很特殊的值，high 跑到 low 前面的时候可能会越界访问 a[0]，low 跑到 high 后面的时候可能会用到 a[n+1]。所以，高级玩家会充分利用这一点，在 a[0] 和 a[n+1] 设置一个特殊的值来简化代码。

5. 二分查找问题的延伸

在上面的例子中，讲述的是查找符合某个条件的数的下标。但是，实际上二分查找算法同样适合于下列问题：

1. 查找数组中满足某个条件的最大的数字。

只要数字的大小和条件成立与否存在单调性，就可以运用二分查找算法。例如，如果只要数字 a 满足题目中的条件，而对所有小于 a 的 b ，都可以推断 b 也是满足条件的。那么，这个问题就类似于二分的右边界查找，我们找出最后一个满足条件的 $x_i$ 。

2. 查找数组中满足某个条件的最小的数字

只要数字的大小和条件成立与否存在单调性，就可以运用二分查找算法。例如，如果只要数字 a 满足题目中的条件，而对所有大于 a 的 b ，都可以推断 b 也是满足条件的。那么，这个问题就类似于二分的左边界查找，我们找出最后一个满足条件的 $x_i$ 。

3. 数组中有多少个数字能满足一个特定的条件。

如果只要数字 a 满足题目中的条件，而对所有小于 a 的 b ，都可以推断 b 也是满足条件的。那么，这个问题就类似于二分的右边界查找，我们找出最后一个满足条件的 $x_i$ ，小于等于 $x_i$ 的数都满足条件，大于 $x_i$ 的都不满足条件，数组又已经有序，所以，满足条件的数就有 i 个。

如果只要数字 a 满足题目中的条件，而对所有大于 a 的 b ，都可以推断 b 也是满足条件的。那么，这个问题就类似于二分的左边界查找，我们找出最后第一个满足条件的 $x_i$ ，大于等于 $x_i$ 的数都满足条件，小于 $x_i$ 的都不满足条件，数组又已经有序，所以，满足条件的数就有 n-i+1 个。