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问道。

“熟能生巧呗。”她回答，“在学校里，每当课余休息时我们都会做二分搜索，我总是能赢。”