5 对一艘走私船的二分搜索（第2/3页）

Frank打断了她，并给了她一个安慰的微笑，他料到是这样的。菜鸟们很少能够处理好他们犯下的第一个错误，而Notation看起来又比大部分人遇到的麻烦更大。“我们正在寻找Retry Loop，”他说，“Crannock夫妇的马车在那个抢劫的夜晚卸下了什么东西，船在19个小时之前已经回来了。”

当然，Frank并不相信她，不过他希望能和她走近一点儿，密切关注她。她所掌握的Crannock夫妇的情况比她写在报告里的东西要多得多。有一些东西在她的报告中没有提及，Frank必须知道她还知道些什么。

“我们最好马上开始，”Notation苦恼地看着码头说道，“有好多船都需要检查。我们是从头开始吗？”港口大部分的船都属于走私犯船，它们很难被区分出来，这些船的名字可能需要挨个去问。

“我们有更好的方法，”Frank解释道，“这里的海关长是个排序狂，他坚持要把港口停泊的船只按照它们到港时间排序。新抵达的船会被安排到一个最接近小镇的船位，这样可以让船员方便地装载和卸货，如果又有新抵达的船，就让所有的船都往后调整，让出最前方的位置。”

“真是可笑，”Notation说道，“多浪费力气！他为什么要这样做？”

Frank笑了笑说：“他声称这是为了效率，但任何在Usb港待了一个星期的人都知道真相。这个海关长受不了腐烂的鱼臭味。港口里那些货物没有全部售完的船，唉……‘香气四溢’。海关长的目的就是要让在港口停留时间长一些的船只远离他的办公室。”

Notation警官瞪着他问道：“你是认真的？”

Frank又笑道：“是的，如果你巡逻过，你也会获得这种有用的信息。现在的关键是我们知道了这里的船是按到港的时间顺序排列的，并且Retry Loop是19小时前抵达的，所以我们就可以简单地做一个二分搜索。

“我们的目标值是19，我们的算法是二分搜索。现在搜索空间是整列船只，所以我们已经有了上界和下界，如果我们使用闭合区间，那么我们的下界是第一艘船，上界是最后一艘船。如果Retry Loop在这里，很明显它不会在第一艘船之前，也不会在最后一艘船之后。

“现在我们从中间的那艘船开始，询问它是何时到港的，如果它的到港时间不足19个小时，那它肯定在Retry Loop之前。这样可以将我们的搜索分为两块，然后……”

“如果它是19个小时以前抵达的，则它一定在Retry Loop之后，”Notation抢在Frank之前说，“我知道二分搜索，我的警用算法课的期末考试就在两个半月之前。”

确定搜索算法后，他们俩就动身去找Retry Loop。中间的船是一艘闻起来有股怪香蕉味的黄色帆船，它是17个小时前抵达的。

这意味着他们可以排除前面一半的船只了，包括中间这艘。Frank将下界调整为黄色帆船之后的那艘船。

搜索空间缩小后，他们选择了一个新的中点。他们花了好一段时间才让这个船长相信他们不是海关的卧底。十分钟之后，Notation将她的徽章推到了船长的眼前，船长的语气立即变得愤怒而抱怨，他说他的船Corrupt Packet已经被困在这个港口22个小时了，要求他们代表他和海关长谈谈。

因为目标是19个小时，所以他们知道Retry Loop是在Corrupt Packet之前抵达。他们又一次改变了界限，所以现在Corrupt Packet左边的船是新的上界。

只剩下两艘船在搜索范围内了，搜索即将结束。如果这两艘船都不是Retry Loop，他们就能确定它已经离开了港口，因为一旦搜索空间没有更多的元素，他们就可以排除整个搜索空间。

因为现在只剩下两艘船，他们可以选择其中任意一个作为中点，根据直觉，Frank选择了早些抵达的船，也就是它们中的下界。与一个在码头闲逛的水手进行简单对话后，他们确定这艘船就是Retry Loop，它已经抵达19个小时了。

“现在怎么办？”他们看着那艘船，Notation问道。

“我们要用你那枚闪亮的徽章。”Frank回答道。

警用算法导论：二分搜索Ⅰ

节选自Drecker教授讲义

二分搜索算法用于高效地在有序数组A中查找一个目标值v。和线性搜索不同，二分搜索利用数据结构中的信息让搜索更高效。高效算法的关键是信息。在下面的例子中，我们就要使用数组是按照升序排序的这个信息：

对于一对索引i和j，如果i<j，则有A[i]≤a[j]