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

Frank摇摇头，咕哝道：“听起来挺好玩的。”

Frank翻到了第202页和203页，发现也都有笔记。“接下来是210页！”Notation说道。

在第210页，他们终于发现这是航行日志的最后一页，上面描述了的最后一次航行的详细记录。“接下来做什么？”Notation问道。

“我们要找到最后一次航行中可疑的包裹或者是港口。这页大约有70个记录，我们要一条一条地看。”

“穷举搜索？”Notation问道，“我们难道不能用一种更高效的方法吗？难道不能把这些记录按照装卸货和交付时间来排序吗？”

“这里不能使用排序。”Frank回答道，“我们不知道每条记录的时间。只有当使用了确定的维度将这些数据排序时，这些排好序的数据才有用。不能按照不确定的维度来进行排序。你想想是不是这样？”

“哦。这是‘天气记录’问题。”Notation说。

“什么问题？”Frank问道。

“这是一个在查找过程中以错误的方法对数据进行排序的例子。”Notation解释道，“Drecker教授给我们举了一个例子：如何在最近十年中找到最冷的一天。如果你将每天的气温日志按照日期时间来排序，你使用二分搜索可以很容易地知道一个指定日期的天气记录。但是这并不能帮助我们找出最冷的一天，所以我们仍然需要浏览每一天的气温记录。”

“我们还是回到现实吧！”Frank说道，“别说那些没有用的，此时你还是找出哪些记录对你有用，哪些对你没有用吧。不要担心，刚才的错误对一个新手来说是很常见的。”

Frank看到Notation对他的话大为恼怒，不禁窃喜，并竭力控制住自己的幸灾乐祸。每个新手在刚出校门时都认为自己无所不知，但是事实证明每个人都还有许多东西需要学习。这次幸好Notation并没有遇到太多麻烦。Frank之前曾经花费很长时间用铲子去铲成桶的猪粪，也正是那个时候，他了解到了二分搜索，那时他也对他的职业选择产生了质疑。

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

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

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

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

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

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

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

节选自Drecker教授讲义

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

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

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

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

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