二分查找——算法、时间复杂度与代码

二分查找是在有序列表中寻找目标值的一种快速方法。你先检查中间项，排除剩余值中的一半，然后重复这个过程。如果列表没有排序，这个逻辑就不成立。

对于升序列表，规则很简单：如果中间值小于目标值，就向右查找；如果中间值大于目标值，就向左查找。因为搜索范围会不断缩小到原来的一半左右，所以二分查找的时间复杂度是 $O(\log n)$。

二分查找如何在有序列表上工作

使用下面这个有序列表：

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

假设目标值是 $31$。

从整个范围开始。中间值是 $24$。因为 $31 > 24$，所以 $24$ 左边的所有元素都可以排除，搜索继续在

$$[31, 39, 45, 52]$$

现在中间值是 $39$。因为 $31 < 39$，所以 $39$ 右边的所有元素都可以排除，于是范围变成

$$[31]$$

现在中间值就是 $31$，所以搜索停止。这里有用的想法不只是找到了目标值，而是只用了两次比较，候选范围就从 $9$ 个值缩小到了 $1$ 个。

为什么二分查找是 $O(\log n)$

每次比较都会排除大约一半的剩余候选项。经过一步后，大约还剩 $n/2$ 个元素。经过两步后，大约还剩 $n/4$ 个元素。经过 $k$ 步后，剩余规模大约是

$$\frac{n}{2^k}$$

当这个量大约变成 $1$ 时，搜索就结束了，因此步数满足

$$2^k \approx n$$

对两边取 $\log_2$，得到

$$k \approx \log_2 n$$

这就是为什么二分查找具有良好的扩展性。线性查找最多可能需要检查 $n$ 次，但二分查找只需要不断把范围减半所需的那些检查次数。

二分查找代码示例

下面是一个标准的 Python 迭代版本：