二分查找

排序把一次比较从“关于一个元素的信息”升级为“关于一整段的信息”：既然 $A[m]<x$，那么 $A[0..m]$ 整段都小于 $x$，一次比较排除一半候选，这正是猜数游戏每问砍半的策略。信息论图像在单调谓词版本中最精确：每次询问 $P(m)$ 只返回真或假一比特，而答案是 $n+1$ 个可能分界位置之一，故最坏至少需要 $\lceil {\log }_2(n+1)\rceil$ 次询问，二分达到同一数量级。精确查找时比较 $A[m]$ 与 $x$ 有小于、等于、大于三种结果，不能逐字说成“一次比较只有一比特”；但受有序结构约束的比较决策树仍给出 $\mathrm{\Theta }(\log n)$ 的最坏界，二分同样在渐近意义下最优。真正的工程难点不在思想而在不变式纪律：区间开闭的语义、中点归入哪一半、每步是否严格缩小区间、重复元素时返回哪一个，都由所选不变式一锤定音，凭感觉增删 $\pm 1$ 是错误的高发路径。定宽整数下 $\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$；此时必须改用单调谓词版的不变式，“相等即停”的写法在重复键上返回的是不确定的某一个出现位置。

未排序的数组没有“排除一半”的依据：在 $[2,9,4]$ 中查找 $4$，中点 $A[1]=9>4$ 会把算法引向左半 $[2]$，与真实位置失之交臂——排序假设一旦缺失，算法安静地给出错误答案而非报错。复杂度结论还依赖 $O(1)$ 随机访问：链表上定位中点本身就要 $O(n)$，二分不再有利。区间必须每步严格缩小：闭区间写法中若用 $m=\lfloor (\ell +r)/2\rfloor$ 搭配 $\ell \leftarrow m$，则在 $r=\ell +1$ 时 $m=\ell$、区间原地不动，循环永不终止。

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

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