二分查找

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

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

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

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

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

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

• 在实数上二分：求 $f(x) = 0$ 的根，$P(x) \equiv (f(x) \ge 0)$，只要 $f$ 连续且变号即可——数组根本不存在。
• 在答案上二分：$P(L) \equiv$「切割长度取 $L$ 时能否得到 $\ge k$ 段」，谓词单调，于是可以二分（下文详述）。
• 在版本号上二分：git bisect 找引入 bug 的那次提交，$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() 里这一行：

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

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

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

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

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

思路与实现#

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

过程：

1. 查看中间元素 arr[mid]
2. 若等于目标，找到，返回
3. 若目标小于 arr[mid]，在左半继续查找
4. 若目标大于 arr[mid]，在右半继续查找
5. 重复直到找到或区间为空

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  # 未找到

写对二分的关键，是先把循环不变量说清楚：每次循环开始时，若目标存在，它一定落在 [lo, hi] 闭区间内；循环结束时区间为空（或 lo > hi），因而可以安全返回“未找到”。凡是改 lo/hi 的赋值，都必须维持这条不变量——lo = mid + 1 与 hi = mid - 1 正是在排除已检查过的 mid 之后，把搜索空间收紧到仍可能含目标的一侧。

开闭区间写法（[lo, hi)）同样正确，但必须整套一致：此时循环条件常写成 lo < hi，取中后若 arr[mid] < target 则 lo = mid + 1，否则 hi = mid（不再减一）。把闭区间模板的细节抄进开区间实现，是线上最常见的“偶发错一个下标”来源。选择一种约定并写满边界用例（空、单元素、全小于、全大于、重复值），比背诵某段“标准代码”更可靠。

复杂度：对数的力量#

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

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

数字直观：

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

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

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

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

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

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

因此，在教学与评审里，与其把“二分很快”当成口号，不如同时报出：比较模型下的下界、跳出模型后的更快算法、以及数据规模小到缓存友好时线性扫描可能反超——三句话齐备，读者才不会把渐近最优误当成一切场景的实测最优。

二分查找的变体#

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

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

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$ 在某区间上从负变正），可以在实数上无限精度地二分。这是数值分析中的"二分法"求根。

重复元素时，“找到任意一个等于 target 的下标”与“找到最左/最右边界”是不同问题。标准相等即返回的写法，在有重复时返回位置不确定；若业务要稳定插入点或统计区间 [L, R) 内的出现次数，就必须改用 lower_bound / upper_bound 一类边界二分，再用两次边界相减得到计数。面试与生产代码里，把这两种需求混为一谈，会导致看似随机的下标错误。

旋转数组变体的教学价值，在于它强迫你显式检查哪一半仍然有序，再决定谓词落在哪侧——这正是“单调谓词”视角的应用，而不是死记“永远砍左边或右边”。一旦旋转点两侧各自有序的性质被破坏（例如无序噪声、多次旋转未还原），二分就会静默失效；因此工程上应先确认输入契约，再套模板。

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

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

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

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

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

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

二分答案能否用，取决于可行性判定 check(x) 对答案变量单调。写题时先问两句：若 x 可行，是否一切更宽松的 x' 也可行？若不可行，是否一切更苛刻的也不可行？两问有一对成立，才能对 x 二分；否则应改用别的搜索或优化方法。判定函数本身的正确性与复杂度同样关键——它若是错的，外层二分只会漂亮地收敛到错误答案。

工程里同类模式随处可见：在分布式系统中对超时阈值、副本数、限流窗口做“最小可行配置”搜索；在资源配置里对容器 CPU/内存上限做能否通过压测的二分。关键习惯是把搜索空间、可行定义、失败时的回退策略写进文档，避免把一次性调参脚本误当成可证明的最优求解器。

代价与争议#

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

缓存：二分的访问序列是 $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(n \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 处理不可判定版本。