精品网站建设电话,站外推广6种方法,即将发布的新品手机,企业个性化网站建设费用本节书摘来自异步社区《编程珠玑#xff08;第2版•修订版#xff09;》一书中的第2章2.2节无处不在的二分搜索#xff0c;作者【美】Jon Bentley#xff0c;更多章节内容可以访问云栖社区“异步社区”公众号查看。 2.2 无处不在的二分搜索我想到的一个数在1到100之间第2版•修订版》一书中的第2章2.2节无处不在的二分搜索作者【美】Jon Bentley更多章节内容可以访问云栖社区“异步社区”公众号查看。 2.2 无处不在的二分搜索我想到的一个数在1到100之间你来猜猜看。50太小了。75太大了。如此游戏进行下去直到你猜中我想到的数为止。如果我的整数位于1到n之间那么你可以在log2n次之内猜中。如果n是1 00010次就可以完成如果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中的选择算法区分出一个随机元素以后就对该元素一侧的所有元素递归地调用自身这是一种随机二分搜索。其他使用二分搜索的地方包括树数据结构和程序调试当程序没有任何提示就意外中止时你会从源代码中哪一部分开始探测来定位错误语句呢。在上述的每个例子中分析程序并对二分搜索算法做些许修改可以带给程序员功能强大的啊哈灵机一动。
