6 二分搜索寻线索
“我们是食品监察员。”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之前曾经花费很长时间用铲子去铲成桶的猪粪，也正是那个时候，他了解到了二分搜索，那时他也对他的职业选择产生了质疑。