形式陈述

给定按全序非降排列的数组 $A[0..n)$ 与目标 $x$，二分查找维护候选区间 $[\ell ,r)$，比较中点

$$m=\lfloor \frac{\ell +r}{2}\rfloor$$

后排除不可能的一半。循环不变式可设为：若目标存在，则其某个合法位置始终位于候选区间；每步使区间长度至少近似减半，比较次数为 $O(\log n)$。

直觉

排序使一次比较的结果能排除整段区间，因此不必逐项扫描。实际难点通常是端点、重复元素和终止条件。

例子与边界

在 $[1,3,3,7,9]$ 中查找 $7$ 可先比较中点。若要找第一个不小于 $x$ 的位置，应维护与“是否存在”不同的不变式。未排序数组没有排除一半的依据。

推论与应用

二分查找也推广为对单调谓词寻找临界点的“答案二分”。复杂度结论依赖随机访问或可高效定位中点的表示。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, §2.3 and exercises。
• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, §6.2.1。