二分查找

排序把一次比较从“关于一个元素的信息”升级为“关于一整段的信息”：既然 $A[m]<x$，那么 $A[0..m]$ 整段都小于 $x$，一次比较排除一半候选，这正是猜数游戏每问砍半的策略。信息论图像在单调谓词版本中最精确：每次询问 $P(m)$ 只返回真或假一比特，而答案是 $n+1$ 个可能分界位置之一，故最坏至少需要 $\lceil {\log }_2(n+1)\rceil$ 次询问，二分达到同一数量级。精确查找时比较 $A[m]$ 与 $x$ 有小于、等于、大于三种结果，不能逐字说成“一次比较只有一比特”；但受有序结构约束的比较决策树仍给出 $\mathrm{\Theta }(\log n)$ 的最坏界，二分同样在渐近意义下最优。

实现时要始终保持同一套区间约定：区间开闭的语义、中点归入哪一半、每步是否严格缩小区间、重复元素时返回哪一个，都应由所选不变式决定。混用闭区间与半开区间的更新式，容易漏掉端点或无法终止。定宽整数下 $\ell +r$ 还可能溢出，稳妥写法是 $m=\ell +\lfloor (r-\ell )/2\rfloor$。

在 $[1,3,3,7,9]$ 中查找 $7$：$\ell =0,r=5$，$m=2$，$A[2]=3<7$，故 $\ell =3$；$m=4$，$A[4]=9>7$，故 $r=4$；$m=3$，$A[3]=7$ 命中——三次比较，而逐项扫描最坏需五次。若改问“第一个不小于 $3$ 的位置”，答案是下标 $1$；其区间依次是 $[0,5)\to [0,2)\to [0,1)\to [1,1)$：两个等于 $3$ 的中点都使右端左移，最后排除 $A[0]=1$。此时必须改用单调谓词版的不变式；“相等即停”的版本只保证返回某个出现位置，不承诺首个或最后一个。固定中点与比较规则后，它的返回位置仍是确定的。

未排序的数组没有“排除一半”的依据：在 $[2,9,4]$ 中查找 $4$，中点 $A[1]=9>4$ 会把算法引向左半 $[2]$，与真实位置失之交臂——排序假设一旦缺失，算法安静地给出错误答案而非报错。复杂度结论还依赖 $O(1)$ 随机访问：链表上定位中点还需指针遍历；谨慎复用区间边界可把总指针移动控制为 $O(n)$，却不会得到数组上的 $O(\log n)$ 总时间。若键比较特别昂贵，减少比较次数仍可能有用。区间必须每步严格缩小：闭区间写法中若用 $m=\lfloor (\ell +r)/2\rfloor$ 搭配 $\ell \leftarrow m$，则在 $r=\ell +1$ 时 $m=\ell$、区间原地不动，循环永不终止。

从优化阈值到最优见证理路从优化阈值到最优见证Optimization to threshold decision · Binary search for optimum · 优化搜索判定归约在有限整数目标和显式上界下二分求最优值，再用受阈值约束的前缀恢复见证，分开核算数值范围与编码成本。明确补足答案二分的两个接口：数值范围 $[0,U]$ 只需 $O(\log (U+1))$ 次判定，但查询编码与判定成本仍收费；得到最优值后，还要通过受该阈值约束的前缀或问题特有自归约，恢复真正达到它的对象。

单调谓词形式把二分从查表扩展为“答案二分”：只要可行性关于参数单调（容量越大越可行之类），就能用对数次可行性判定逼出最优值，这是把判定器升级为优化器的通用手法。连续版本是实数区间上的对分法，依托介值定理理路介值定理Intermediate value theorem连续函数在实区间上不能跳过中间高度；由完备性证明存在性，并厘清二分法、唯一性和不动点迭代。逼近方程的根，每步把包围根的区间长度减半。结构化版本是二叉搜索树理路二叉搜索树Binary search tree · BST每个结点左子树键小于、右子树键大于该结点键的二叉树。，把中点比较固化为指针分叉以支持动态插删。而“每次比较至多一比特信息”的计数论证，同样是比较排序下界理路比较排序下界Comparison sorting lower bound任何最坏情形比较排序都需 Ω(n log n) 次比较。的核心。

若许多单调判定都依赖同一份更新历史，批量二分理路批量二分Parallel binary search · 离线批量二分 · 并行二分把多个单调查询的二分中点按更新日期分桶，每轮从同一初态重放一次，以共享判定状态求各自首次达标时间。把各自中点按日期分桶，每轮只从初态顺扫重放一次。每条查询仍维持本页的首真边界；共享的是昂贵的判定状态，不是用离线条件替代单调性，也不要求多处理器。

本页的 $O(\log n)$ 是有序数组、常数时间随机访问和比较模型下的最坏查询界。前驱问题理路Word-RAM 前驱问题Predecessor problem在 Word-RAM 的有限整数宇宙中维护有序集合，并查询不大于给定键的最大成员。把“找最后一个不超过 $x$ 的键”提升为可跨模型比较的接口，整数 Word-RAM 能利用键的 bit 结构突破普通比较树路线；分数级联理路分数级联fractional cascading在相关有序目录间建立采样桥，使一次完整二分后可常数时间转移位置。在许多相关有序表之间复用一次定位，把重复二分的成本压到一次对数加线性表数。若数据主要驻留外存，缓存无关搜索树理路缓存无关搜索树cache-oblivious search tree在程序不知道块大小与缓存容量时，通过递归布局使搜索在各级存储上同时获得对数块传输界。关注的是块传输而非比较次数。三者都从二分的分界思想出发，却改变了问题批次或机器模型。

galloping归并理路短段驱动的galloping归并Galloping merge · Exponential-search merge · 跳跃归并 · 短段驱动归并以较短有序段为驱动，用指数探测和二分批量越过长段前缀，证明稳定边界及按跳跃长度计费的比较界。从上一次边界按偏移0、1、3、7、…探测，夹住目标后再运行本页二分。若这次只跨过d项，比较数是O(1+log(d+1))，而非每次都按整个长段长度计费；相等键使用lower还是upper边界，由原左记录必须先出的稳定合同决定。