物理

信息竞赛中的一些算法：二分查找

这是一个关于信息竞赛的帖子（应该可以发在 O-Box 里吧）

符号约定：

$A\to B$ 表示把 $A$ 的值设为 $B$。

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

一位学生背着一个装了 $n$ 本书的背包，走出了图书馆。

这时，警报器响了。学生打开背包，拿着其中一本书走过大门，警报器没响。

他拿起另一本书，走过大门，警报器还是没有响。

保安有些不耐烦了，他把书分成两份，拿起其中一半，走过大门，警报器响了。

他把这一半书再次分为两份……

很快，保安找到了那本书。他用鄙视的眼光看着学生：“你难道不知道 $O(\log n)$ 比 $O(n)$ 快吗？”

第二天，图书馆丢失了 $n-3$ 本书。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

这个故事讲的不是二分查找的原理和优缺点，是为了说明二分查找更快。

假设我们有一些排好序的数据，想从中找出你想找的数，就可以用二分查找。

假设数据是这样的：

0:0 1:1 2:2 3:3 4:4 5:5 6:6 7:7（冒号左边是编号，右边是数据）

假设你想找到 $2$，怎么办呢？

先定义 $l\to0,r\to8$ 表示寻找的范围，一开始肯定是全部。（注：范围包括 $l$ 不包括 $r$）

然后定义 $m\to[\frac{l+r+1}{2}]=4$ 作为这个区间最中间的数（$[x]$ 是 floor 函数）

比较 $2$ 与第四个数 $4$ 的大小：$2\lt4$

然后 $r\to4$

$m\to[\frac{l+r+1}{2}]=2$

比较 $2$ 与第二个数 $2$ 的大小：$2=2$

于是查找完成。

不完整代码：

int a[8] = {0, 1, 2, 3, 4, 5, 6, 7}

int l = 0, r = 8;

while (a[m] != 2) {

    m = (l + r + 1) / 2;

    if (a[m] > 2) {

        r = m;

    } else if (a[m] < 2) {

        l = m + 1;

    }

}

cout << "a[" << m << "] = 2" << endl;

当然，我们可以继续优化……

假设有 $2^n$ 个数，最慢需要循环 $n$ 次。易得：

有 $\frac12$ 的可能循环 $n$ 次；

有 $\frac14$ 的可能循环 $n-1$ 次；

有 $\frac18$ 的可能循环 $n-2$ 次；

有 $\frac{1}{2^k}$ 的可能循环 $n-k+1$ 次。

求个平均值：

$\sum_{k=1}^{n+1}\frac{1}{2^k}\cdot(n-k+1)$

$=\sum_{k=1}^{n+1}\frac{1}{2^k}\cdot{n}-\sum_{k=1}^{n+1}\frac{1}{2^k}\cdot(k-1)$

$=n-\sum_{k=1}^{n+1}\frac{k-1}{2^k}$

$\gt n-2$

也就是循环次数的平均数大于 $n-2$。

如果把代码改成这样：

int a[8] = {0, 1, 2, 3, 4, 5, 6, 7}

int l = 0, r = 8;

while (l<r) {

    m = (l + r + 1) / 2;

    if (a[m] > 2) {

        r = m;

    } else {

        l = m + 1;

    }

}

cout << "a[" << m << "] = 2" << endl;

这样也可以实现查找。

虽然它每次一定循环 $n$ 次，但它每次循环可以减少 $1$ 次比较，当 $n$ 较大时更快。