“我们是食品监察员。”Frank与Notation警官一边大步流星地踩着狭窄的跳板上船，一边喊道。在Frank的示意下，Notation迅速地挥了挥她的工作证，快得根本来不及让人看清楚证件上写的是什么。
“食品监察员？”一位船员疑惑地问道，“我们并没有运送任何食物啊。”
Frank把这位船员打量了一番，他看起来不像是船长，也不像是被雇佣的保安，他可能只是一位水手，当船长不在的时候就由他负责。这在走私船上很常见，因为如果雇佣安保人员来看守货物，那会显得太招摇了。
Frank冲着那位水手吼道：“我们要查查看。我可听说这条船上有一批腐烂的鳗鱼，我就是来查这批鳗鱼的。”
“鳗鱼？”那位水手对此显然非常疑惑。
“腐烂的鳗鱼！”Frank马上答道，“我们要到下面去查查。”没等对方回答，他就朝着舱口大步走去，准备走下甲板。
Notation连忙紧随其后。
“咱们时间不多，趁着他们船长还没回来，咱们得赶紧找到这条船的航行日志。”Frank边下梯子边说道，“航行日志上有货单，上面会记录运过的货物及抵达过的港口。货单肯定造过假，因为走私船上从来不会记录真实的货物。但如果读得够仔细的话，我们说不定能发现一些蛛丝马迹。”
Notation在货舱后面找到了航行日志，她把它抽了出来。Frank仔细看了看封面，上面写着如下信息。
货单及Retry Loop日志
船长：A.James
船籍港：Usb
船主：Vinettee家族航运集团有限公司
没想到在成功避开Vinettee集团围捕的几个月后，这次Frank竟然又歪打正着地上了他们的一条船。Frank本能地四处查看货舱，看有没有藏起来的党羽，或改装成武器的农具，或者有没有鼻涕虫比赛的痕迹。Frank打消了最后一种想法的可能性，因为大家都知道鼻涕虫不会在船上赛跑，它们好像不喜欢在满是盐水的环境里赛跑。
他摇摇头，继续把注意力集中到眼前的问题上。Frank必须在Vinettee集团的人得知他上船之前找到点线索，不然他有可能又下不了船了。他立即把航行日志翻到最后一页，然后开始一页一页往前翻。
Notation问道：“你在做什么？”
“我在找最后一次的航行日志记录。”Frank回答。
“一页一页地找？”Notation问道，“这本日志一共有1000页，为什么你不使用二分搜索的方法？就是我们在两分钟之前刚刚使用过的方法。”
Frank停了下来。虽然他并不是寻找某个特定页码，但是他仍然可以使用二分搜索的方法找到这条船的最后一次航行日志。他可以根据当前页是否有文字记录来减少搜索范围。
“好的。那就使用二分搜索的方法。”Frank同意了。
Frank再次打开航行日志，并翻到最后一页。在确定这本日志正好1000页后，他设定这本日志的页码下界为1，上界为1000。他得出中间值是500，然后翻到了第500页。
他发现第500页和501页都是空白，因此Frank知道了这本航行日志的最后一次航行记录必然在第499页或之前。现在他把第499页设为新的上界值。然后再次算出中间值为250，并翻到第250页。他发现第250页竟然又是空白。
“这看起来像一本新的日志啊。”Notation说，“还好你刚才没有从最后一页一页往前翻。”
此时，Frank根本没空理她。他再把下界值设为1，上界值设为249，并算出中间值125，并立马翻到了125页。这次他找到了笔迹，由此可以断定，最后一次航行日志的记录必然在125页之后，因此他将下界值调整到125。最后一条记录必然在125~249页之间。
“187页！”在Frank在脑海里计算出中间值之前，Notation便脱口而出。Frank翻到了第187页，发现这页也有文字记录，看来187页也不是最后一次航行记录，应该还在187~249页之间。于是他继续调整下界值为187。
“218页！”Notation说道。该页竟然还是空白页，那么最后一条记录必然在187~217页之间了，因此Frank将下界值和上界值分别改为187和217。
“202页！”在Frank将上下界值相加之前，还没来得及计算中间值，Notation又脱口而出。
“你为什么算得这么快？”Frank问道。
“熟能生巧呗。”她回答，“在学校里，每当课余休息时我们都会做二分搜索，我总是能赢。”
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美元的交易，但是这并不能帮助你找出特定的交易日期、交易号或交易者姓名。
1 鼻涕虫遇到盐就会化成水你信不信？请移步这里http://www.ahalei.com/thread-9150-1-1.html，友情提示画面太美哦——译者注返回