Usb港看起来就像是一个渔村。远远地看去，在码头的尽头矗立着一群破旧的建筑。每当有船只抵港时，这里才会有一些零星的活动，平时这个小镇显得非常宁静。
Frank直接向Crab’s Pinch走去，那是一个渔夫酒吧，以蛤砺海鲜浓汤和每周三晚上的船夫号子大赛而出名。如果幸运的话，今天他的一个老朋友将会出现这里。毕竟，Crab’s Pinch是Usb港唯一一个可以去的地方。现在，Frank选择后排角落里的一个桌子坐下了，点了一份海鲜浓汤等待着。
不久前一个名叫Mavis的走私犯来过这个潮湿的小酒吧。由于天生小心谨慎，Mavis从来没有被抓到过。不过众所周知的是，她曾经不惜烧毁她的船以销毁证据。但Frank与她私交甚好，至少在Frank离开警队后，他们会交换一些零碎的信息。
Frank对着他的浓汤度过了漫长的一个小时后，终于看到了Mavis，他推开碗向Mavis打了一声招呼。Mavis在门口犹豫了一会儿，挤过人群进入酒吧。
“Mavis，”当她走到这个角落后，Frank说道，“你好吗？”
“十分钟之前比现在好多了！”她生气地啐出这几个字。
Frank还没来得及问任何问题，Notation警官就大步跨进了门，她举着手大声说道：“女士们先生们，大家请注意！两天前的晚上有一辆马车路过这里。”
Frank低声咒骂着，他受够了她的这种官腔。
“我从天没亮就跑来这，本希望能有一碗热乎乎的海鲜汤和几分钟的安静，却看到了警察在找什么笨蛋马车！”Mavis抱怨道。
Frank笑了笑：“所以在她走掉之前，你都不能卸货，对吧？”
Mavis瞪了Frank一眼，但也没有什么可以反驳的。Usb港从来就没有人是靠捕渔和航运来赚钱的。这个港口对于罪犯来说的确很有吸引力，他们可以把心思都花在运送货品上，而无须应付那些“多管闲事”的政府官员。Frank敢用他一个月的租金打赌，在这个码头没有一条船是不走私的。
“你知道什么有关那辆马车的事情吗？”Frank轻声说。
Mavis耸耸肩：“这里的码头上总有马车。这里是一个港口，Frank，人们要运送货物。”
“这是一辆特殊的马车，”Frank追问，“马车上有一串独立的可以存放动物的棚，就像一个装在轮子上的巨大的数组。”
“听起很高级的样子，”Mavis说，“可我从没听说过有什么动物被运送。倒是听说过关于运送一些箱子或者两只小乌龟的传闻，但没什么东西大到需要用棚来运送。你确定它经过这里？”
Frank点点头。那个马车的味道就像是厕所里的鱼味空气清新剂，有时候闻起来就像Usb港的味道一样差劲。
“那这几天有船离开过这里吗？”Frank问。这些小偷把偷来的文件运送到这么远的地方，他们不会一直傻等着的。
“只有Retry Loop这艘船离开过，”Mavis说，“我只能告诉你这些，因为这是公开的。但是我并不知道它装了些什么，我也不关心。”
“那你知道它什么时候回来的吗？”Frank问。
“19个小时以前回到港口的，”Mavis回答，“我还是不知道它装了些什么。”
Frank大笑着说：“看来我应该去镇上逛一逛了。”
Mavis敷衍地笑了笑后向服务员打了个手势。
Frank沿着码头走了不到20米，Notation警官就跑过去跟上了他。
“Runtime先生，我在调查一个案子，”她开口道，“如果你有关于……”
Frank停了下来，使得她也猛地停住脚步。“Notation警官，你在调查什么？”Frank问道。
Notation嘴唇动了几下，没有发出任何声音，但此时她的脖子突然变得通红。
Frank又问：“警长并不知道你在这里，对吗？你在这里调查并没有得到警长的许可。”
“你是什么意思？”Notation警官反驳道，但是Frank打断了她。
“别装了，”Frank说，“你单独来到这里这一事实就我的证据。你在擅自进行调查。可问题是你为什么要调查此案呢？”
此刻，Notation警官变得越发面红耳赤。
“这不是你该关心的事。”她说。
“警长能来找我，就说明他已经不相信自己的人了。”Frank冷静地回答。
“警长竟然聘请了你这种过气的侦探？”
“是的，因为他相信我。”
Notation警官板起脸，眼里露出怒气。不一会儿，Frank甚至觉得她也许会用她的警棍来结束这次谈话。但是她很快就消气了，就像她来气时一样快。
“我需要找到那些文件，”她伤心地说，“这是我的错——那晚是我值班。”
“明白了。”Frank若有所思地说。
“我必须找到那些文件，”Notation警官又重复了一遍，听起来有点激动，“我刚到警队才几个月，并且……”
Frank打断了她，并给了她一个安慰的微笑，他料到是这样的。菜鸟们很少能够处理好他们犯下的第一个错误，而Notation看起来又比大部分人遇到的麻烦更大。“我们正在寻找Retry Loop，”他说，“Crannock夫妇的马车在那个抢劫的夜晚卸下了什么东西，船在19个小时之前已经回来了。”
当然，Frank并不相信她，不过他希望能和她走近一点儿，密切关注她。她所掌握的Crannock夫妇的情况比她写在报告里的东西要多得多。有一些东西在她的报告中没有提及，Frank必须知道她还知道些什么。
“我们最好马上开始，”Notation苦恼地看着码头说道，“有好多船都需要检查。我们是从头开始吗？”港口大部分的船都属于走私犯船，它们很难被区分出来，这些船的名字可能需要挨个去问。
“我们有更好的方法，”Frank解释道，“这里的海关长是个排序狂，他坚持要把港口停泊的船只按照它们到港时间排序。新抵达的船会被安排到一个最接近小镇的船位，这样可以让船员方便地装载和卸货，如果又有新抵达的船，就让所有的船都往后调整，让出最前方的位置。”
“真是可笑，”Notation说道，“多浪费力气！他为什么要这样做？”
Frank笑了笑说：“他声称这是为了效率，但任何在Usb港待了一个星期的人都知道真相。这个海关长受不了腐烂的鱼臭味。港口里那些货物没有全部售完的船，唉……‘香气四溢’。海关长的目的就是要让在港口停留时间长一些的船只远离他的办公室。”
Notation警官瞪着他问道：“你是认真的？”
Frank又笑道：“是的，如果你巡逻过，你也会获得这种有用的信息。现在的关键是我们知道了这里的船是按到港的时间顺序排列的，并且Retry Loop是19小时前抵达的，所以我们就可以简单地做一个二分搜索。
“我们的目标值是19，我们的算法是二分搜索。现在搜索空间是整列船只，所以我们已经有了上界和下界，如果我们使用闭合区间，那么我们的下界是第一艘船，上界是最后一艘船。如果Retry Loop在这里，很明显它不会在第一艘船之前，也不会在最后一艘船之后。
“现在我们从中间的那艘船开始，询问它是何时到港的，如果它的到港时间不足19个小时，那它肯定在Retry Loop之前。这样可以将我们的搜索分为两块，然后……”
“如果它是19个小时以前抵达的，则它一定在Retry Loop之后，”Notation抢在Frank之前说，“我知道二分搜索，我的警用算法课的期末考试就在两个半月之前。”
确定搜索算法后，他们俩就动身去找Retry Loop。中间的船是一艘闻起来有股怪香蕉味的黄色帆船，它是17个小时前抵达的。
这意味着他们可以排除前面一半的船只了，包括中间这艘。Frank将下界调整为黄色帆船之后的那艘船。
搜索空间缩小后，他们选择了一个新的中点。他们花了好一段时间才让这个船长相信他们不是海关的卧底。十分钟之后，Notation将她的徽章推到了船长的眼前，船长的语气立即变得愤怒而抱怨，他说他的船Corrupt Packet已经被困在这个港口22个小时了，要求他们代表他和海关长谈谈。
因为目标是19个小时，所以他们知道Retry Loop是在Corrupt Packet之前抵达。他们又一次改变了界限，所以现在Corrupt Packet左边的船是新的上界。
只剩下两艘船在搜索范围内了，搜索即将结束。如果这两艘船都不是Retry Loop，他们就能确定它已经离开了港口，因为一旦搜索空间没有更多的元素，他们就可以排除整个搜索空间。
因为现在只剩下两艘船，他们可以选择其中任意一个作为中点，根据直觉，Frank选择了早些抵达的船，也就是它们中的下界。与一个在码头闲逛的水手进行简单对话后，他们确定这艘船就是Retry Loop，它已经抵达19个小时了。
“现在怎么办？”他们看着那艘船，Notation问道。
“我们要用你那枚闪亮的徽章。”Frank回答道。
警用算法导论：二分搜索Ⅰ
节选自Drecker教授讲义
二分搜索算法用于高效地在有序数组A中查找一个目标值v。和线性搜索不同，二分搜索利用数据结构中的信息让搜索更高效。高效算法的关键是信息。在下面的例子中，我们就要使用数组是按照升序排序的这个信息：
对于一对索引i和j，如果i<j，则有A[i]≤a[j]
这看起来并不是很多的信息，但是它足够让我们的搜索更加高效。
二分搜索算法的工作原理是：不断地将搜索空间分成两半，并且把搜索空间限制在其中的一半中。这个算法通过改变上下界限有效地限制了搜索空间。上界（IndexHigh）标记了搜索空间有效数组中最高的索引，下界（IndexLow）标记了搜索空间有效数组中最低的索引。通过这个算法，如果目标值在这个数组中，就可以保证：
在搜索的每一步中，我们只需依次判定上界和下界中间的值：
接下来，我们将中间值A[IndexMid]和目标值v进行比较。如果中间值小于目标值（A[IndexMid]<v），我们就知道目标值一定介于这个中间值之后。这样我们可以将IndexLow改为IndexMid+1来使搜索空间又变成原来的一半。
如果中间值比目标值大（A[IndexMid]>v），我们就知道目标一定位于中间值之前，于是我们将IndexHigh改为IndexMid-1来使得搜索空间变成原来的一半。
当然，如果我们发现A[IndexMid]等于v，我们可以直接结束搜索，找到目标值。
现在我们就来使用二分搜索在下面这个已排序的数组中寻找到15。虚线框出的方块是算法当前需要判定的值，而被阴影遮住的部分则是在搜索中被排除的部分。
第一个被判定的中点的值是11，比我们的目标值15小。因为我们知道这个数组是按照升序排列的，所以可以排除中点及其之前的所有部分。我们将下界索引移动到适当的地方（IndexLow=IndexMid+1）。
在第二次比较之后，我们发现中点值是52，比目标值大。我们可以排除中点和它之后的所有部分。此时需要移动我们上界（IndexHigh=IndexMid-1）。
请注意，通过这几次的操作，此时虽然下界已经是目标值了（v=15），但是我们仍需要继续搜索，直到中间值指向目标值。这是因为二分搜索是对中间值进行判定，而不会判定上界和下界是否是目标值。
如果目标值不在数组中会发生什么呢？在搜索过程中，上下界之间的距离会越来越近，直到它们之间没有任何还未检查过的值。因为我们总是将其中一个界限移动到中间值的另一边，所以我们可以在IndexHigh<Indexlow的时候停下来，这个时候就可以保证目标值不在数组中了。