跳转到内容
← 返回算法
经典算法计算机科学 · 算法约 16 分钟阅读

二分查找

Binary Search

在 1000 页的字典里查一个单词，没有人会从第一页开始逐页翻。人们翻到中间，判断目标词在左半还是右半，然后对着那半部分重复这个动作——几步就找到了。 这就是二分查找（Binary Search）的本质。它是最简单、最优雅的算法思想之一，也是"搜索有序结构"这类问题的理论最优解。

二分查找搜索算法对数时间分治

在 1000 页的字典里查一个单词，没有人会从第一页开始逐页翻。人们翻到中间，判断目标词在左半还是右半，然后对着那半部分重复这个动作——几步就找到了。

这就是二分查找（Binary Search）的本质。它是最简单、最优雅的算法思想之一，也是"搜索有序结构"这类问题的理论最优解。

破除误解一：二分的前提不是"有序数组"，是"单调谓词"

这是关于二分查找最值得纠正的一条理解。教科书总说"二分查找要求数组有序"，于是很多人以为二分是一个关于数组的算法。它不是。

二分真正需要的东西只有一个：一个取值范围上的布尔谓词 $P$，它在某点之前恒为假、之后恒为真（或反过来）。形式化地说，存在一个分界点 $k$ 使得

P(0),P(1),…,P(k−1)=false,P(k),P(k+1),…=trueP(0), P(1), \ldots, P(k-1) = \text{false}, \qquad P(k), P(k+1), \ldots = \text{true}

二分做的事就是找这个分界点，每次比较砍掉一半候选。有序数组只是这个框架最常见的一个特例：P(i)≡(arr[i]≥target)P(i) \equiv (\texttt{arr}[i] \ge \texttt{target})，数组有序恰好保证了 $P$ 单调。

这个视角一换，二分的适用范围立刻扩张：

  • 在实数上二分：求 $f(x) = 0$ 的根，P(x)≡(f(x)≥0)P(x) \equiv (f(x) \ge 0)，只要 $f$ 连续且变号即可——数组根本不存在。
  • 在答案上二分：P(L)≡P(L) \equiv「切割长度取 $L$ 时能否得到 ≥k\ge k 段」，谓词单调，于是可以二分（下文详述）。
  • 在版本号上二分：git bisect 找引入 bug 的那次提交，P(commit)≡P(\text{commit}) \equiv「这个版本是否已经坏了」。它需要的不是提交按什么排序，而是"坏了之后就一直坏着"这个单调性。
  • 在时间上二分：数据库按时间戳定位日志位点、监控系统定位故障起始时刻，同理。

不满足单调性时二分会静默给出错误答案——它不会报错，只会返回一个看起来合理的位置。git bisect 遇到间歇性 bug（同一版本有时过有时不过）就是这个失效模式的现实版本，也是它需要 git bisect skip 的原因。

破除误解二：它比看起来难写得多

高德纳（Donald Knuth）在《计算机程序设计艺术》中提到：二分查找的思想于 1946 年就已发表，但第一个完全正确的实现直到 1962 年才出现——中间隔了十六年。

这个说法常被当成趣闻，但它指向一个真实的工程难题：二分的边界条件（lo vs lo + 1、< vs <=、区间开闭、取整方向）组合起来有十几种写法，其中大部分是错的，而且错法往往只在特定输入下暴露（空数组、单元素、目标不存在、目标在两端）。

2006 年的实例最有说服力。 Google 工程师 Joshua Bloch 发表博文《几乎所有二分查找和归并排序都是坏的》，指出 JDK 的 Arrays.binarySearch() 里这一行：

java
int mid = (low + high) / 2;   // ← 有 bug
```

当 low + high 超过 231−12^{31} - 1 时，32 位有符号整数溢出成负数，mid 变成负下标，抛出 ArrayIndexOutOfBoundsException。正确写法是

java
int mid = low + (high - low) / 2;   // 或 (low + high) >>> 1
```

这个 bug 在 JDK 里存活了九年。为什么这么久才被发现？因为触发它需要数组长度超过约 2302^{30}——十亿个元素。1998 年没人有那么大的数组；到 2006 年，有了。Bloch 在文中写道，他自己在《Effective Java》里也讲过二分查找，同样没注意到这一点。

这件事的分量：一个只有五行、被写进所有教科书、被无数人 review 过的算法，其标准库实现带着一个溢出 bug 跑了九年。它说明代码的正确性会随着运行环境的变化而失效——当年那行代码在当年的数据规模下确实是对的。

思路与实现

前提：数组必须是有序的。

过程：

  1. 查看中间元素 arr[mid]
  2. 若等于目标，找到，返回
  3. 若目标小于 arr[mid]，在左半继续查找
  4. 若目标大于 arr[mid]，在右半继续查找
  5. 重复直到找到或区间为空
python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # 避免整数溢出
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1  # 未找到
```

复杂度：对数的力量

每次查找把搜索范围缩小一半。$n$ 个元素最多需要 ⌈log⁡2n⌉\lceil \log_2 n \rceil 次比较：

T(n)=T(n/2)+O(1)  ⟹  T(n)=O(log⁡n)T(n) = T(n/2) + O(1) \implies T(n) = O(\log n)

数字直观：

数组大小 $n$线性查找最坏次数二分查找最坏次数
1,0001,00010
1,000,0001,000,00020
1,000,000,0001,000,000,00030

对 10 亿个元素，二分查找只需 30 次比较。对数增长是极其缓慢的——这意味着数据量翻倍，只增加 1 次操作。

这也是为什么有序结构（排序数组、平衡二叉搜索树、B-Tree）如此重要：它们把搜索从线性变成对数，在大规模数据上带来质的差异。数据库索引的本质，就是把查找从 $O(n)$ 变成 O(log⁡n)O(\log n)。

而且这个 log⁡2n\log_2 n 无法再改进——这是一条下界，不只是一个上界。 论证来自信息论：每次比较的结果只有两种（大于 / 不大于），因此提供至多 1 比特信息。要在 $n$ 个元素中确定目标位置（外加"不存在"这一种可能），需要区分 $n + 1$ 种结果，即至少 log⁡2(n+1)\log_2(n+1) 比特。所以任何基于比较的搜索算法，最坏情况下至少需要 ⌈log⁡2(n+1)⌉\lceil \log_2(n+1) \rceil 次比较。

二分查找正好达到这个界，因此它是最优的——在比较模型下。这个限定词很关键：换一个模型，界就变了。

  • 插值查找（Interpolation Search）：不盲目取中点，而是按数值大小按比例估计位置（就像查字典时"S 开头的词大概在四分之三处"）。对均匀分布的数据，期望比较次数降到 O(log⁡log⁡n)O(\log \log n)——10 亿个元素只需约 5 次。它凭什么突破下界？因为它不只做比较，还读取了键的数值并做算术，跳出了比较模型。代价是数据分布不均匀时会退化到 $O(n)$。
  • 哈希表：$O(1)$。它同样不做比较，而是计算哈希值——又一个跳出模型的例子。

看到一条下界时，第一件事是问它成立于哪个模型。 下界从不禁止你换模型，只禁止你在同一模型内做得更好。

二分查找的变体

标准二分查找找到目标就返回。实际问题常常更复杂：

找左边界（第一个 ≥\geq target 的位置）：

python
def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # 即使 target 不存在，返回它"应该插入"的位置
```

这个变体在面试中极常见，也是很多高阶算法的子程序。C++ STL 的 lower_bound() 和 upper_bound() 实现的就是这两种变体。

旋转有序数组：数组 [3, 4, 5, 1, 2] 是把有序数组 [1, 2, 3, 4, 5] 旋转后的结果，仍然可以用二分查找（需要分情况判断哪半部分是有序的）。

实数域上的二分：不只适用于整数下标，只要搜索域上存在单调性，就可以二分。例如，求方程 $f(x) = 0$ 的根（若 $f$ 在某区间上从负变正），可以在实数上无限精度地二分。这是数值分析中的"二分法"求根。

二分答案：把最优化问题转化为判定问题

二分查找最强大的工程应用之一，是解决"最小化/最大化"问题。

技巧：如果答案满足单调性（答案越大越容易满足某条件，或越小越容易），可以把"求最优答案"转化为"对答案二分，每次判断这个答案是否可行"：

例：给 $n$ 块木板，每块长度已知，用一台木材切割机设定切割长度 $L$，切割后每块木板被截成 $\lfloor \text{长度}/L \rfloor$ 段，求至少能得到 $k$ 段木头的最大切割长度 $L$。

直接求 $L$ 很复杂，但对于给定的 $L$，判断"能否得到至少 $k$ 段"是 $O(n)$ 的简单计算。因为"可行的 $L$"随着 $L$ 增大单调减少，可以对 $L$ 二分，共需 O(nlog⁡(max_length))O(n \log(\text{max\_length}))。

这种把优化问题转化为判定问题的技巧，在算法竞赛和工程系统中极为常见。

代价与争议

  • 有序性要求：二分查找只适用于有序结构。维护有序性本身有代价——动态数据集插入删除时需要保持排序。哈希表提供 $O(1)$ 查找，但不支持范围查询和有序遍历。两者是不同的权衡。
  • 对缓存与分支预测的双重不友好——这一条比通常讲的更严重，值得展开。

缓存：二分的访问序列是 n/2→n/4→3n/8→⋯n/2 \to n/4 \to 3n/8 \to \cdots，前几次跳跃的跨度远超缓存行（通常 64 字节），几乎每次都是一次缓存缺失，且地址无规律可循，硬件预取器完全帮不上忙。所以对小数组（约十几个元素以内），线性扫描通常更快——它顺序读取，一次缓存行加载就覆盖十几个元素。这正是 std::sort 等标准库在递归到小区间时切换成插入排序的同类理由。

分支预测：更隐蔽的一条。二分每一步的 if (arr[mid] < target) 结果本质上是不可预测的（近似五五开），现代 CPU 的分支预测器命中率接近随机，每次预测失败要清空十几级流水线。也就是说，二分不仅在等内存，还在浪费已经取到的指令。

怎么修：Khuong 与 Morin（JEA 2017）系统测量了各种数组布局与搜索实现，结论是两条改动最有效——(1) 用条件移动指令（cmov）替代分支，把"跳转"变成"无分支的算术选择"，彻底消除分支误判；(2) 改用 Eytzinger 布局，即把二叉搜索树按 BFS 顺序（根、两个孩子、四个孙子……）平铺进数组，于是搜索路径上相邻的几层落在同一批缓存行里，并可显式 prefetch 下几层。在大 $n$ 上，这套组合比朴素二分快出可观倍数。

教益：比较次数已经触到信息论下界，无法再减；但每次比较的代价还有很大压缩空间。算法优化在触底之后，战场就从"操作数"转移到"每次操作花多少纳秒"。 - "已排序"假设的隐性代价：如果数据原本无序，需要先排序（O(nlog⁡n)O(n \log n)），再用二分（O(log⁡n)O(\log n)）。只查一次时，不如直接线性扫描（$O(n)$）。二分的价值在于多次查询同一个有序集合。

跨域连接

  • 贝叶斯定理：每步砍掉一半，前提是目标位置服从均匀分布，此时中点让两侧后验各为二分之一。先验不均匀时最优切点就不是中点，而是把后验概率均分的那个位置。按数值比例估位置的插值查找正是这个思路，它对均匀分布把比较次数压到对数的对数级，代价是分布偏斜时退化成线性扫描。
  • 哈希：两者的差别不在速度而在能力。哈希抹掉了顺序，因此回答不了"最接近的键是谁""这个区间里有哪些键"；有序结构保留顺序，所以下界查询天然可用。选择标准是需不需要范围查询，而不是哪个渐进更快——这也是数据库既建哈希索引又建有序索引的原因。
  • 版本控制：在提交历史上二分定位引入缺陷的那次提交，需要的不是提交按什么排序，而是"坏了之后就一直坏着"这条单调性。间歇性缺陷会破坏它，而破坏之后二分不会报错，只返回一个看起来合理的提交。这是它最危险的失效模式，也是工具必须提供跳过不可判定版本的原因。
  • 筛查与早期发现：混样检测把"谁是阳性"的搜索压到对数量级的检测次数，前提同样是单调谓词——阳性池必含阳性个体。它的收益随患病率下降而上升：流行率低时一次混检排除一大批人，流行率一高，几乎每个池都是阳性，分组反而多做了检测。这个拐点可以直接算出来，是公共卫生的常规计算。
  • 滴定分析：滴定寻找等当点，靠的是那里的指示量陡变——把连续的浓度轴变成近乎二值的"是否已过量"。这正是二分能用的物理条件：谓词必须在某点干净地翻转。缓冲体系会把陡变抹平，翻转不再清晰，逐步逼近随之失效，只能改用整条曲线拟合。判据是否单调且陡峭，决定了方法能不能用。

参考文献

  • Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching. 2nd ed., §6.2.1. Addison-Wesley, 1998.（含二分查找的历史与各变体的精确比较次数分析）
  • Bloch, J. Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Google Research Blog, 2006 年 6 月.（JDK 整数溢出 bug 的第一手报告）
  • Khuong, P.-V. & Morin, P. Array Layouts for Comparison-Based Searching. ACM Journal of Experimental Algorithmics 22, article 1.3 (2017). arXiv:1509.05053.（Eytzinger 布局、无分支实现与预取的系统实测）
  • Perl, Y., Itai, A. & Avni, H. Interpolation Search — A Log Log N Search. Communications of the ACM 21(7), 550–553 (1978).
  • Sedgewick, R. & Wayne, K. Algorithms. 4th ed., 第 1 章. Addison-Wesley, 2011.

延伸阅读

  • Bentley, J. Programming Pearls. 2nd ed., Addison-Wesley, 2000.（第 4 章用二分查找作为"如何写出可证明正确的代码"的范例，与第 2 章的二分应用互为呼应）
  • Git 文档：git-bisect(1)，含 bisect run 自动化与 bisect skip 处理不可判定版本。

正文中引用本条 · 3 · 其中 2 条来自其他领域

数学华罗庚连续性