6 二分搜索寻线索（第2/2页）

大约三分钟后，他们找出了唯一的线索。Retry Loop最近有两次可疑的停靠，Mudwall港口和Frayed Cable岛。即使是走私人员，停在这两个地方也非常奇怪。Mudwall港口依托一个偏远又满是泥浆的农场，还经常吹嘘其少之又少的贸易量。Frayed Cable岛更加荒凉：这是一座岩石小岛，岛上仅有一座建筑——现在已经废弃的IronRing监狱。

“这里，”Frank指着日志说道，“这就是他们拿走你文件的地方。Mudwall港口或Frayed Cable岛。他们可能在一个地方丢掉文件后在另外一个地方提取款项。”

“你怎么知道的？”Notation问道，她看起来很怀疑，“难道我们不应该考虑所有港口……”

Frank打断她的话：“我们没有时间找出所有港口。”他没有详细解释。他使用他自己发明的算法，即启发式搜索，虽然在当船长时这种算法曾让他陷入麻烦，但是他有一种直觉，并且他坚信这种直觉。

“你确定……”Notation正要问，但是被他们上方的声音打断了。

Frank没有说话，但是可以很清楚地认出这声音。麻烦来了。

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

节选自Drecker教授讲义

使某个算法有效的关键因素是信息。对于二分搜索，我们得了解有待排序的数据的相关信息，以便知道数据是按照什么方式排序的。为了排除（或缩小）较大查找范围，所使用的算法必须能够保证我们要找的目标值不在被去除的范围内。

但是，按照某个维度对数据排序后，并不意味着你可以按照另一个维度对数据进行二分搜索。例如，你正在查找某个记账单，以便找出线索。记账单是使用交易号来排序的，这表明交易被按照记录时间来排序了。这意味着每个条目的交易号都小于其后面条目的交易号。如果当前条目的交易号为105，则这个条目之前的所有条目的交易号都小于105，其之后的所有条目的交易号都大于105。

但是，这也意味着条目的其他字段（如交易的实际日期、交易者姓名或交易金额）并未按一定的顺序排列。如果你想要找出特定可疑金额的对应交易或者使用已知军火商找出相关交易，要怎么办呢？这时现有的排序是否有用？没用，你需要使用详尽的线性查找。

虽然你知道Zed咖啡馆发生了编号为105的交易，但是这并不能让你知道该场交易前后的交易的交易者信息或交易金额。

同样道理，如果你按照交易金额递增的顺序来排列账目，则可以快速找出所有价值为250美元的交易，但是这并不能帮助你找出特定的交易日期、交易号或交易者姓名。

1. 1 鼻涕虫遇到盐就会化成水你信不信？请移步这里http://www.ahalei.com/thread-9150-1-1.html，友情提示画面太美哦——译者注返回