2.2 无处不在的二分搜索
我想到的一个数在1到100之间，你来猜猜看。50？太小了。75？太大了。如此，游戏进行下去，直到你猜中我想到的数为止。如果我的整数位于1到n之间，那么你可以在log2n次之内猜中。如果n是1 000，10次就可以完成；如果n是100万，则最多20次就可以完成。
这个例子引出了一项可以解决众多编程问题的技术：二分搜索。初始条件是已知一个对象存在于一个给定的范围内，而一次探测操作可以告诉我们该对象是否低于、等于或高于给定的位置。二分搜索通过重复探测当前范围的中点来定位对象。如果一次探测没有找到该对象，那么我们将当前范围减半，然后继续下一次探测。当找到所需要的对象或范围为空时停止。
在程序设计中二分搜索最常见的应用是在有序数组中搜索元素。在查找项50时，算法进行如下探测。
众所周知，二分搜索程序要正确运行很困难。在第4章中我们将详细研究其代码。
顺序搜索在搜索一个具有n个元素的表时，平均需要进行n/2次比较，而二分搜索仅仅进行不超过log2n次的比较就可以完成。这在系统性能上会造成巨大的差异。下面的故事来自于《ACM通讯》的实例研究“TWA Reservation System”。
我们有一个执行线性搜索的程序，可以在1秒钟内对一块非常巨大的内存块完成100次搜索。随着网络的增长，处理每条消息所需的平均CPU时间上升了0.3毫秒，这对我们来说是巨大的变化。我们发现问题的根源是线性搜索。把程序改为使用二分搜索以后，该问题消失了。
我在许多系统中也遇到过相同的问题。程序员在开始的时候使用简单的顺序搜索数据结构，这在开始的时候通常都足够快。当搜索变得太慢的时候，对表进行排序并使用二分搜索通常可以消除瓶颈。
但是二分搜索的故事并没有在快速搜索有序数组这里终止。Roy Weil将该技术应用于清理一个约1000行的输入文件，其中仅包含一个错误行。很不幸，肉眼看不出错误行。只能通过在程序中运行文件的一个（起始）部分并且观察到离奇错误的答案来辨别，这将会花费几分钟的时间。他的前任调试人员试图通过每次运行整个程序中的少数几行程序来找出错误行，但只在取得解决方案的道路上前进了一点点。Weil是如何仅仅运行10次程序就找到罪魁祸首的呢？
经过前面的热身，我们现在来攻克问题A。输入为顺序文件（考虑磁带或磁盘——虽然磁盘可以随机读写，但是从头至尾读取文件通常会快得多）。文件包含最多40亿个随机排列的32位整数，而我们需要找出一个不存在于该文件中的32位整数。（至少缺少一个整数，因为一共有232也就是4 294 967 296个这样的整数。）如果有足够的内存，可以采用第1章中介绍的位图技术，使用536 870 912个8位字节形成位图来表示已看到的整数。然而，该问题还问到在仅有几百个字节内存和几个稀疏顺序文件的情况下如何找到缺失的整数？为了采用二分搜索技术，就必须定义一个范围、在该范围内表示元素的方式以及用来确定哪一半范围存在缺失整数的探测方法。如何来实现呢？
我们采用已知包含至少一个缺失元素的一系列整数作为范围，并使用包含所有这些整数在内的文件表示这个范围。灵机一动的结果是通过统计中间点之上和之下的元素来探测范围：或者上面或者下面的范围具有至多全部范围的一半元素。由于整个范围中有一个缺失元素，因此我们所需的那一半范围中必然也包含缺失的元素。这些就是解决该问题的二分搜索算法所需要的主要想法。在翻阅答案查看Ed Reingold是如何做的以前，请尝试将这些想法组织起来。
对于二分搜索技术在程序设计中的应用来说，这些应用仅仅是皮毛而已。求根程序使用二分搜索技术，通过连续地对分区间来求解单变量方程式（数值分析家称之为对分法）。当答案11.9中的选择算法区分出一个随机元素以后，就对该元素一侧的所有元素递归地调用自身（这是一种随机二分搜索）。其他使用二分搜索的地方包括树数据结构和程序调试（当程序没有任何提示就意外中止时，你会从源代码中哪一部分开始探测来定位错误语句呢？）。在上述的每个例子中，分析程序并对二分搜索算法做些许修改，可以带给程序员功能强大的啊哈！灵机一动。