二分查找

在 32 个有序值里找一个数，有两条路。线性扫描把目标之前的每个下标都读一遍；二分查找只读一个下标，扔掉一半数组，然后重复。拖滑块移动目标，比较两边的次数：

注意扫描的代价就是目标自己的位置 —— 把它放到下标 31，它要花 32 次比较 —— 而二分查找无论目标在哪，都不会超过 6 次。省下来的不是因为它挑位置挑得聪明，而是因为它每一次比较都值一整个「剩下的一半」。

下面是同一个查找，数组画成阶梯 —— 因为有序看起来就是阶梯的样子。虚线是目标自己的高度;探针要么在它上面、要么在它下面，判断就这么点内容。拖轴上的手柄，再用琥珀色滑块一次一次地走比较：

注意下面那道括号在干什么。它是「还可能装着目标」的下标集合，而且一个都不会弄丢：每次迭代开始时，如果目标真在数组里，它的下标就落在 [lo, hi] 内。每个分支都保住它 —— a[mid] < target 意味着到 mid 为止的每个下标都太小，所以 lo = mid + 1 丢掉的东西里没有一个可能是答案。

代价也是从这个不变式里出来的。从长度 n 的区间里删掉 mid, 一边剩 ⌊(n−1)/2⌋，另一边剩 ⌈(n−1)/2⌉，所以最坏的幸存者是 ⌊n/2⌋。拖动 n，数一数有几级：

因为最坏情况满足 T(n) = 1 + T(⌊n/2⌋),从 n 一路到空的链条正好有⌊log₂ n⌋ + 1 级 —— 32 是 6 级，64 是 7 级，1,024 是 11 级。这是一个计数论证，而不是「它对半嘛」这种说辞：递归在区间变空时触底。把 n 放到一条每走一格就乘同一倍数的轴上，把手柄拖到十亿：

在那条轴上，比较次数是一条笔直的阶梯 ——n 每翻一倍就多一级，一百万时 20 级，十亿时 30 级 —— 而下面那个数字就是扫描要读的次数。空间是三个下标 —— lo、mid、hi —— 无论 n 多大。

二分查找不需要有序数组。它需要更弱的东西：它在 mid 处问的那个是非问题一旦为真，就得在之后每个下标上都保持为真。有序只是安排出这件事最常见的方式。拖动目标，看数组下面那条答案带:

注意这条带子永远是 F…FT…T，绝不会是 F T F T —— 对任何目标都成立，包括越过末尾的那个。这才是真正的前提：谓词是单调的，数组的唯一职责就是让它单调。这一页剩下的内容，都是在那条带子上找边界。lower_bound、upper_bound、「能行的最小 k」和「旋转点」, 是同一个循环配四个问题。

那前提不成立会怎样？不会抛异常。下面是一个有序数组，其中有一根柱子可以动；查找要找的是41，它自始至终都在下标 10。把 a[9] 抬到超过它：

越过 41 的时候盯住读数。在 33 以下，数组已经乱了，查找却仍返回正确的下标 —— 这种 bug 能上线正因如此：测试数据走了乱序不影响结果的路径。到 41 以上，同一个查找对一个确实在数组里的值返回 −1，什么都不报。它是安静地失败的，你最后拿到的那个栈来自完全不相干的地方。

所以前提条件真正有用的读法是谓词，而不是数组。下面是同一个数组旋转之后 —— 除了两段之内，哪儿都不有序 —— 而 a[i] ≥ a[0] 这个问题依然单调。转动旋转量，看第一个假:

注意这条带子是 T…TF…F —— 上一条的镜像，一样能二分。第一个假就是最小值的下标，正是 LC 153 和 LC 33 要的；而在零旋转时没有假，循环返回 n。前提条件从来就不是数组：构造一个你能证明其单调的谓词，才是所有难变体里的主要工作。

第一个是算术。lo 和 hi 都是合法下标，所以各自都装得进一个 int —— 但它们的和未必。把数组长度拖过 2³⁰, 看那根条越界：

看越过之后 (lo + hi) / 2 返回什么。在 32 位补码里和会回绕成负数，右移也保住了负号 —— 到 2³¹ − 1 个元素 时，中点算出来是 −3。lo + (hi − lo) / 2 用一个不可能溢出的差算出同一个中点。这不是假想：java.util.Arrays.binarySearch 带着错误版本发布了九年， Joshua Bloch 2006 年那篇文章正是今天大家都写第二种的原因。 2³⁰ 个元素的 int[] 是 4 GiB —— 1997 年荒唐，现在很平常。

第二个决定是区间约定。闭区间 [lo, hi] 说两端都是候选；半开区间 [lo, hi) 说 hi 是末尾的下一个。让同一个「第一个真」的查找在两种约定下一起走，盯住两个 hi 标记:

注意它们各自站在哪。闭区间的 hi 永远指向一个格子；半开区间的那个指向格子之间的缝, 不用发明不存在的下标就表达了「最后一个下标的下一个」。收尾也不同：闭区间停在 lo = hi + 1, 半开区间停在 lo = hi，答案都在 lo 里。混用，就是 while (lo <= hi) 配上 hi = mid 的由来。

而那正是那个永不终止的 bug。每个分支都必须严格缩小存活区间；在闭区间循环里，当 lo、hi 和探针是同一个下标时，hi = mid 并不缩。先用安全规则走一遍，再切到坏的那个：

看第 4 步之后的括号。用 hi = mid − 1, 区间会变空、循环会结束；用 hi = mid，它就永远卡在一个候选上，读数会数它在那儿耗了几步。在生产环境这不是崩溃，而是一个跑满的核和一个永不返回的请求，任何只检查返回值的测试都抓不到。同一套检查也能抓住它的镜像：存活分支写成 lo = mid，而中点朝错的方向取整：

用 mid = lo + (hi − lo) / 2，一旦 hi 等于 lo + 1,探针就落在 lo 上，lo = mid 把 lo 赋给自己，区间不再缩小。向上取整就是全部的修复。对每个分支证明区间严格更小，并在 hi == lo + 1 上试一遍。

区间约定定下来之后，半开区间版本只有六行，而且没有一个容易忘记更新的 ans 变量：lo 和 hi 本身就是答案的括号，它们相遇时，lo 就是谓词第一次为真的下标。走一遍，再把谓词从 ≥ 切到 >:

注意这个开关对循环没有任何改变，对lo 停在哪却是全部改变。a[i] ≥ 8 停在第一个 8;a[i] > 8 停在最后一个 8 的下一个下标。这两个就是 lower_bound 和 upper_bound, 而「最后一个 8」是 upper_bound − 1 —— 你永远不用另写一个「最右」查找，也永远不用写闭区间版本需要的那套 ans = mid 记账。

于是数个数就是白送的。两个边界把整段相等值夹住，它们的差就是有几个：两次查找，不用扫描，哪怕这一段占满整个数组也还是 O(log n)。把目标在这些值之间移动，再移到一个不存在的值上：

因为这两个边界是插入位置而不是元素位置，对不存在的值它们也有定义 —— 这时两者相等，括号塌成一条线，个数是 0。这同时也是「在不在」的判定：i = lower_bound(x); i < n && a[i] == x。精确匹配是特例，边界才是通例，而且只有边界能组合。把一个区间的两端拖一拖，看个数跟着走：

注意下界和上界现在回答的是两个不同的问题，而个数无非是它们的差：upper_bound(hi) − lower_bound(lo)，两次查找，不用扫描，哪怕区间覆盖整个数组也一样。把两端都推过 20，括号塌成一条线 —— 空区间数出 0 而不是报错，因为插入位置处处有定义。

Koko 有四堆香蕉 —— 3、6、7、11 —— 以及守卫回来前的八小时。以速度 k，她吃完 p 根的一堆要 ⌈p/k⌉ 小时，因为她一小时之内不会开第二堆。拖动速度，数一数被切成几口：

注意底下那条带子又是 F…FT…T。它必须是：吃得更快永远不会更慢，所以一旦某个速度来得及，更大的速度都来得及。正是这个单调性 —— 而不是有序性，这里根本没有有序数组 —— 构成全部前提。候选答案是 1 … max(堆)，每次判定谓词要扫一遍所有堆，所以整体是 O(堆数 · log 最大堆)。

于是把同一个半开区间的「第一个真」循环跑在速度上，而不是跑在下标上。括号现在是一段答案区间，mid 是一个还没人试过的速度：

看括号怎么收在 4 上 —— 四次探测，而逐个试要试 十一 个候选速度。一大类问题都是这个形状：最小运载量、最少天数、最小除数，以及所有「让最大值最小」的问题。难的从来不是查找，而是找到谓词并证明它单调；而当它不单调时，循环照样会返回一个东西 —— 安静地, 跟数组乱序时一模一样。

答案轴还给了你一样数组给不了的东西：它不必有界。没有天然上界时，就把边界翻倍，直到谓词变真, 再在你跳过的那段区间里做二分。拖动答案，把两个阶段都数一数：

因为翻倍最多超出一倍，二分阶段花的不会比翻倍阶段更多 —— 答案在 a 时大约 2·log₂ a 次探测，全程不假设任何上界。这就是指数查找，也是 std::equal_range 在前向迭代器上干的事，以及 Timsort 在某一段连赢时进入 galloping 模式干的事。

二分查找最初的几次探测彼此相隔半个数组，所以每一次都落在自己那条 64 字节缓存行上；而扫描每条行读十六个 int32，按地址顺序，硬件预取器把这部分开销完全藏起来了。拖动 n, 把琥珀色的行数和扫描要流过的那些行比一比：

注意查找的尾巴挤进了同一条行：64 字节装得下十六个 int32, 所以最后那几次探测落进的是已经在 L1 里的那条行 —— 读数会数出几次，而且并不固定：没对齐的十五个元素照样跨两条行。在 1,024 个值 时是 10 次探测碰 6 条行；2²⁰ 是 19 次碰 16 条 —— 其中大部分是预取器预料不到的缺失，因为每个地址都取决于还没算完的那次比较。

给它安上数字。扫描一个元素 0.25 ns —— AVX2 比较在约 3.5 GHz 下每周期退休好几个 —— 二分查找一次探测 2.5 ns，那是预测器学不会的数据相关分支，约一半时间失败、每次约 15 周期；哈希查找固定 12 ns；碰数组的那两种各加 2 ns 调用开销。把 n 拖过交叉点：

因为这条轴每走一格就把 n 乘上同一个倍数，二分查找的开销每翻一倍只上一级台阶，而扫描的直往上翘 ——哈希那条固定 12 ns，才是图上唯一的直线。把赢家读出来：扫描撑到大约 40 个元素，再往上，滑块能到的每个 n 上都是哈希最便宜 —— 在 1,024 个值 时它是 12 ns，查找 30 ns，扫描 258 ns。在这个模型里二分查找从来没有单独赢过。你选它，是为了另外两者答不上来的问题：

看一个数组里没有的值会怎样。哈希没有东西可还，而同一个 lower_bound 依然说得出前驱、后继和插入位置 —— 换成 一个确实在里面的值，它连「在不在」也一并回答了。顺序，正是哈希扔掉的东西。

# pred(i) 成立的第一个下标；都不成立就返回 n
lo, hi = 0, n                      # 半开区间 [lo, hi)
while lo < hi:
    mid = lo + (hi - lo) // 2      # 不会溢出
    if pred(mid):  hi = mid        # mid 仍是候选
    else:          lo = mid + 1    # mid 被排除
return lo                          # == hi;n 表示「没有真的下标」

下面就是它跑在 16 个格子上，边界由你的手控制。格子上方的数字是它探测的先后顺序。先在中间拖一拖，再把它推到 末尾之外，以及 下标 0:

注意两端都照样有答案。lo 是插入位置而不是元素，所以 n 表示「没有为真的下标」、0 表示「全都是」, 都是合法返回值 —— 这也是这个循环不需要空输入特判的原因。

循环从来不检查它唯一依赖的那件事。把带子里某一个答案改错，它照跑不误、照样停机，照样返回一个下标：

注意整个过程什么都没出错。每次探测都在界内，每个分支区间都在缩，返回值也是合法下标 —— 只是它不是第一个为真的那个，有些翻转位置上还碰巧是对的。循环内部加不了断言：单调性是整条带子的性质，而循环只看到 ⌊log₂ n⌋ + 1 格。下面三个 bug，是能活着通过评审的那三个：

• (lo + hi) / 2 → lo + (hi − lo) / 2。 元素数超过 2³⁰ 时，前者返回负下标。
• while (lo <= hi) 配 hi = mid。 在 lo == hi 处空转。闭区间用 mid − 1。
• 谓词不单调。 不抛异常，也不越界 —— 就是给你一个答案，有时候还是对的。