作者：Jeremy Kubica
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
算法神探：一部谷歌首席工程师写的CS小说试读：
译者序
算法！Algorithms！
咳咳！很多人一听到这个词，估计脑袋就要炸了：一定又是复杂极了的东西，看来此书必定翻不过第一节，就要睡着了。
没错，很多算法书虽然写得很精妙，但凭我这种智商一口气最多只能看5到10页，就会乖乖滚回去睡觉了。不少读者说《啊哈！算法》一口气能读100页，这已经是极限。那么，这本《算法神探：一部谷歌首席工程师写的CS小说》或许可以一口气读完，没错，是读完！
整本书巧妙地将算法穿插入一场离奇的盗窃案的侦破中。没有一行代码和公式，取而代之是一场又一场鲜活的破案游戏，带你游走在各个犯罪现场，让你身临其境地观察我们的主人公是如何使用算法搜寻线索并逐步揭开事实真相的。虽然这本书并不是教科书，但通过这种轻松的阅读学习，你可以对算法的本质有大致了解。在酣畅淋漓地读完本书之后，再去翻阅其他算法书籍，你会惊奇地发现，自己竟然可以看懂那些枯燥苦涩的代码和公式了。
其实，在阅读本书之前，你甚至不需要掌握任何编程的基础知识。这并不影响你阅读全书，并以轻松有趣的方式了解这些算法——就是这样一本神奇的算法书。
然而，时间紧张加之我们翻译水平有限，请恕不能将原作者的精巧行文完美地展现在你面前。译文中难免有不足和疏漏之处，还请不吝批评指正。翻译期间得到了不少朋友的帮助，在此向他们表示感谢。特别感谢我的挚友丁广浩，他目前就职于美国的Amazon。在On-Call Duty的日子里面，他还抽时间帮我解答疑问，甚是感激。另外，也非常感谢武汉外国语学校的张竞文同学和浙江大学的陈泓宇同学。
好嘞，故事要开始了，让我们跟随Frank探长和Notation警官一起走入这场奇妙之旅。啊哈磊ahalei.com
关于作者
Jeremy Kubica在Google任职首席工程师，着力于机器学习和算法方向。他拥有康奈尔大学的计算机科学本科学位和卡耐基梅隆大学的机器人专业博士学位。在研究生期间，他设计了一个算法，可以探测对地球有威胁的小行星（当然，还尚未能阻止那些小行星）。Kubica同时也是著名博客Computational Fairy Tales的作者。
关于技术审校者
Heidi Newton拥有新西兰坎特伯雷大学计算机科学专业的学士学位，以及新西兰惠灵顿维多利亚大学计算机科学专业的硕士学位。她目前就职于坎特伯雷大学计算机专业的代码复仇者研究小组，并在业余时间进行相关辅导和咨询工作。她目前致力于改善关于计算机科学和编程的教学资源。
致谢
我要对所有支持本书和为本书做出了贡献的人们深表感谢。
首先，我想向No Starch出版社团队的所有人致谢。特别是Liz Chadwick和Riley Hoffman在本书的编辑过程中给予我的帮助、指导和建议。Liz高质量的建议使得本书的故事内容保持了流畅清晰。同时，我也很感谢她提出的将本书涉及的专业内容以讲义形式呈现的建议。感谢Bill Pollock和Tyler Ortman的支持，特别感谢Bill为本书书名提供的建议。也感谢Carlos Bueno向我介绍了No Starch出版社。
感谢Miran Lipovaca为本书提供了精美的插图。这些插图很好地刻画了本书的人物特色和故事情节。
感谢Heidi Newton从专业角度进行的细致深度的审校。她的审阅很大程度上确保了本书所涵盖的内容和概念能够以准确易懂的方式呈现出来。非常感谢她针对书中的晦涩难懂处给予的提醒。
同时也感谢所有阅读过本书早期手稿并提供了宝贵建议的人：John Bull、Mike Hochberg、Edith Kubica、Regan Lee和Kristen“Kit”Subbs博士。感谢Ilana Schwarcz对于本书早期手稿的编辑，以及对本书在行文上的建议和帮助。
最后，我想由衷地感谢我的家人，特别是父母在我孩童时期对于我的计算机兴趣的支持，以及对我写作本书给予的鼓励。
导读
本书关注的是计算机思维和搜索算法。这些故事介绍并阐释了较高层次的计算机思想，探索了它们背后的动机及其在非计算机领域中的应用。本书并不奢望对算法进行非常详尽而全面的描述，书中的故事也不是为了替代计算机科学中那些坚实而严谨的技术性描述。相反，它们的作用更像是插图：对整体思想进行补充，帮助你更好地理解算法。
本书介绍了一系列的计算方法，它们大致上属于搜索算法的范畴。书中每一章首先通过一个故事来讲解算法的大致思想，随后再用讲义的形式来对算法进行更为技术性的解释。读者可以完全跳过这些技术讲解部分，同时又不会错过任何一个精彩的故事。
本书假定你已经对一些基本的计算机科学思想有所了解，但你并不需要掌握任何一门编程语言。本书中的算法适用于各种编程语言和不同领域的问题。1 搜索问题
没听见敲门声，门竟然开了——只有大门铰链的嘎吱嘎吱声宣告了有人到访。Frank立马起身欲取来十字弓，却又骤然停住，他想若是Vinettee集团的人登门造访，一定会敲门——不过是用斧头。进门者无论是谁，想必都有话要说。于是，Frank伸手拿起马克杯，将杯底仅剩的那点冷掉的咖啡一饮而尽。“Donovan警长，”Frank看到来访者说道，“是什么风把您吹到这片和谐的街坊来了？我还以为您再也不敢越过第15号街了呢。”“好久不见，”Donovan警长简短地说道，“Frank，别来无恙？”“好极了。”Frank干巴巴地答道，同时盯着在屋里缓缓踱步的Donovan警长。
Donovan警长扫视着Frank寒酸的办公室，他红色的警官披风在身后沙沙作响。“私家侦探的游戏玩得可好？”“够还债。”Frank在说谎。
Donovan警长点了点头。他稍作停顿，然后转向书柜，看了看书柜上的书。“您这次来算是探访故人了？”Frank说道，“那我应该问候一下Marlene和孩子们的近况吧？”“他们好得很，”Donovan警长头也不回地答道，“Marlene的海龟美容生意这些日子做得不错。Bill去年加入警队了。Veronica在做会计，我们最后本该……”“我只是随便问问。”Frank打断了Donovan警长的话。
Donovan警长耸耸肩。他从书架上抽出一本书，随意翻了起来。Frank伸长脖子瞧了瞧封面——《警察学院年鉴：第21班》。“你想要什么，Donovan警长？”Frank问道。
Donovan警长与Frank对视了一下，“我需要你的帮助，Frank。”他说。
Frank直起了身子。在Frank离开警队后的五年间，Donovan警长一共上门见了他两次，两次都是来警告他别再插手案件。这次Frank也已经做好了被威胁的准备，但现在，Donovan警长似乎遇到了特殊的问题——帮助解决这种程度的问题，或许可以用报酬还清Frank拖欠的房租。“我早就不是警队的人了，”Frank漫不经心地说道，“你怎么不派个你信得过的侦探去接手？”“我需要警队之外的人，”Donovan警长说道，“别装了，Frank。如果你不清楚我上这儿来意味着什么，那你也不是我需要的人。”
Frank笑了：“出内鬼了？在你的队里？”“更糟。昨晚有人闯进局里的档案室，偷走了五百多份卷宗。”“他们想找什么呢？”Frank问道。坐在椅子上的他，不假思索地往前探身，并迅速地抄起一卷新羊皮纸和一杆羽毛笔。Frank对这一系列的动作已驾轻就熟，就如同喝咖啡和爬楼梯一般。“我不知道，”Donovan警长说道，“无迹可循！他们偷了整架整架的文件，从财产纠纷的文件到费用报表。我们记录的有关杀手、名流、私家侦探、司法人员的分类文件，统统被他们拿走了……甚至连农夫Swinson的两筐噪声投诉信也被他们拿去了。但奇怪的是，其余架子他们连碰都没碰。据我们统计，至少丢失了512份文件。”“没准是农夫Swinson的某位邻居干的，”Frank打趣道，“他们一定是听说了，但凡超过100封投诉信，就会有实习生到你家给你严厉地上上课。”
Donovan警长懒得理他，他只是可怜地瞪着眼，直到Frank清了清嗓子，才打破沉默：“所以，你想让我去找回这些文件？”
Donovan警长摇摇头说：“我想让你找出那些贼。我们有文件的备份。我想知道，他们想要什么信息，打算用来做什么。”“是一个搜索问题啊。”Frank若有所思地说。当年在警队时，Frank的两大特长就是解决搜索问题，以及惹怒Donovan警长。“国王知道了吗？”Frank问道。“我昨天已向国王简要禀报过了，”Donovan警长说道，声音中透出一丝不悦，“自打那个疯癫癫的巫师闹过之后，国王坚决要求对诸事进行每日简报。”两年前，一个名为Exponentious的狂妄巫师曾企图摧毁整个王国。此后，Fredrick国王亲自制定了全面的措施，以提升王国的安全。他为此颁布了三百多条新的安全法规，其中至少有五条是关于十层以下政府大楼内的公文保管的。“这也不能怪他，”Donovan警长嘟囔道，“当时真是挺险的。多亏有Ann公主，否则谁知道王国今天是何种境地。”
Frank默默点头。当年Exponentious巫师对研究算法的学者们施下诅咒，从而袭击了王国的算法基础。短短几个月的时间，就连简单的操作都被他搞得低效不堪，王国逐渐濒临停转。损坏的迹象随处可见，甚至在当地的面包店里，Frank都亲身目睹了恐慌爆发，因为顾客们发现，他们都想不起来如何排成一个队列了。“当然了，国王对此问题也抱有个人兴趣，”Donovan警长生气并急躁地说道，“他想知道所有的细节：谁在负责此案？我们在用哪些搜索算法？我们是否搜遍了所有相邻的建筑物？”
Frank强忍住笑，开始仔细考虑这个问题。为首都的警察部队客串一回顾问，应该能拿到不少钱。他低头瞥了一眼自己的脚，一根脚趾头已经快从鞋子的破洞里露出来了。“如果让我做顾问，”他说，“那就得按我的方式来。”
决定性的关键就在这儿了。五年前他被踢出警队，就是因为他太按自己的方式做事。而Donovan警长是个信奉规则和命令的人。Frank上一次使用了启发式搜索，也是最后的那根稻草——于是就在当天下午，Donovan警长收回了他的警徽。不过，话又说回来，按Frank的方式做事总能得到结果。“不出我所料。”Donovan警长最终答道。他从披风式风衣下抽出一份薄薄的文件夹，丢在Frank的桌上。“我会跟你联络的。”Donovan警长说。然后，他毫无任何表示地转身离开了办公室。
在接下来的三个小时内，Frank喝了12杯咖啡，此时他弓身伏坐在桌前，第七次翻阅着这份薄薄的信息文件夹。文字在摇曳的烛光中跳动摇摆，却未能显示任何新的信息。
线索并不多。Donovan警长给他的是丢失文件的清单及事发当晚的值班名册，仅此而已。
最后，Frank夸张地叹了口气，抓起一张羊皮纸，开始做笔记。
任何搜索问题的第一步，都是确定你想找到的东西——目标，他的老教练在警用算法导论课上是这么称呼的。Frank很早就吸取了这个教训：他在成为警官的第一个星期，就被任命去找回公爵的名贵种马，结果那天下午他带了一只42磅重的海龟得意地回到警局。显然，这只抢眼的爬行动物不是目标。如果你找错了东西，那算法再好也毫无意义。
这一次的案件中，问题不在于是什么，而在于是谁。Donovan警长在这一点上说对了。一旦贼拿到了文件，警方就算找回来也于事无济。因为贼已经获得了他们想要的任何信息。
所以，他的目标很简单：弄清楚是哪个人或哪些人偷走了文件。
任何搜索问题的第二步，都是确定搜索空间。你要搜哪里？Frank每天找自己的钥匙时，搜索空间是办公室里的所有平坦表面。而当Frank想找出一个犯罪分子时，他的搜索空间则是首都附近的每一个人。
Frank坐了回去，揉了揉眼睛。这是一个很大的搜索问题——要在犯罪之都找到一个特定的罪犯。不过他遇过更糟的情况。
既然他已经明确了问题，那么现在他可以开始选择算法了。线性搜索首先出局，因为他可没能耐去审问城里的每一个人。他还可以排除掉过去在学院里学来的很多其他的花哨算法。对于这样的问题，他必须回到自己的基本搜索算法工具包，这是私家侦探最值得信赖的朋友。
Frank在羊皮纸上写下一条笔记。他有了寻找的目标，知道了搜索空间，现在也确定了算法，是时候开工了。警用算法导论：搜索问题
节选自Drecker教授讲义
在本课程中，我们将讨论几种不同的算法（以及相关的数据结构），来解决搜索问题。搜索问题的定义为：任何需要我们在可能的空间范围（搜索空间）内，找到一个特定值（即目标）的问题。
等你们将来毕业成为警察后，每天都会遇到可被归为搜索问题的问题。搜索问题的广义定义涵盖了很多不同的计算问题，例如“在警察日志上搜索某一特定条目”这样的简单搜索，以及“从窝点中找到房间”，乃至“找出符合某些条件的所有逮捕记录”这样的复杂搜索。这个类别是无法穷举的，但是在后面，我会给你们讲解一些基本和重要算法的简单例子。
该类别中所描述的算法拥有下面三个共同元素。
目标：你所寻找的那条数据。目标可以是一个特定的值，或是一条表示搜索成功完成的标准。
搜索空间：用于探测目标的所有可能性的组。例如，搜索空间可以是一份数值列表，或是图中的所有节点。搜索空间内的单个可能性被称为状态。
搜索算法：用于进行搜索的一组具体步骤或指令。
部分搜索问题会有额外的要求或复杂性，在我们学习不同的算法时将会逐一谈到。2 穷举搜索寻线人“高效算法的关键在于信息。”这是Drecker教授的口头禅，在每一堂警用算法课的开始，他都会冲学员厉声强调这句话，Frank对这句话的印象如此强烈，以至于将它永久封存在了自己的记忆中：“一个好的算法取决于发现数据中的结构并善加利用。而这取决于信息。”
回忆至此，Frank暗地里微微一笑，此时他走在了三比特街巷，这是一条坑坑洼洼的泥土路，两旁交相排列着破旧的酒吧和高档的咖啡厅。他冲两位路过的骑士礼貌地点点头，骑士们身着盔甲走过时还发出锵锵的响声。Frank暗自盘算着，待会儿在离开之前，必须要来杯三倍特浓的意式咖啡。首先，他需要的是信息，来帮助指导搜索。他很确切地知道要从哪里开始。“玻璃箱”Billy此时一定在某处静静地坐着，倾听着屋内飘荡的每一段对话。人们并非成心想在Billy身边说这说那的，其实是压根没注意到他的存在。Billy被赐予了一种特别值得一提的天赋，那就是彻彻底底的不显眼。不管做什么，Billy身上总有一种东西，能让人们注意不到他。或许是他的白皮肤或小身板，或许是他对穿着分外平庸的品味。不管是什么，Billy早已决定，要充分发挥他的天赋，窃听并收集信息，再卖给任何愿意收购的人。
Frank打量着三比特巷上挤在一块儿的八个店面，琢磨着Billy会选其中哪一个。他在脑中思考了半打的搜索算法，但一无所获，没有任何信息可以用来确定Billy的位置。Billy有可能在其中任意一家酒吧或咖啡馆中。
他不得不采用穷举搜索了——索性试遍所有的可能性，直到他找到Billy。这其实不太适合他。多年的侦探和私人调查经历已经让他明白，几乎所有算法都优于穷举搜索算法，而他厌恶诉诸如此低效的方式。
Frank一边抱怨，一边开始了搜索。他走进了街上的第一家酒吧，名字叫Absolute Value。
酒保是一个名叫Abe的粗暴男人，从Frank一进门便瞪着他，目的明确地把手放到满是划痕的吧台下面。信息很明确：“我正握着武器，至于是哪种，你猜去吧。但如果你找我麻烦，我会让你尝尝滋味的。”“我不是来找茬的，Abe，”Frank说道，举起双手，“我只是来这儿见Billy的。”“那好，Billy不在这儿。”酒保说道。
Frank几乎如释重负地一笑，说道：“那我就撤了。”
Abe草草地点了点头，看着Frank离开，手仍然留在吧台下面。
Frank做了几下深呼吸，在微凉的空气中摇摇头。Abe记仇的时间比Frank见过的其他任何人都长。不过话又说回来，Frank已经逮走了Abe的四个兄弟姐妹。
街上的下一个店面是Brazen Boolean，这是一间现代化的咖啡厅，拥有典型的布尔类型风格——鲜明的黑白两色。布尔市的居民素以狂热倾心于逻辑的绝对概念而闻名，在他们眼中，一切事物要么为真，要么为假。他们是很称职的目击者。作为镇上唯一的布尔咖啡厅，Brazen Boolean是那些背井离乡者的避风港。毕竟，在布尔人眼中只有两种人：布尔人和其他人。
Frank把头伸进门内，向在场的所有人问道：“Billy在这儿吗？”沉默了一会，20双眼睛仔细地扫视了咖啡馆内的每一个角落。如非绝对肯定，布尔人是不会回答问题的。“不在。”传来了确切的答复。
Frank继续他的穷举搜索。
第三和第四家店铺的经历虽然明显更令人愉快，但同样无果而终。第三家店Constant Const的酒保热情地欢迎了Frank，并邀请他一道怀念过去的美好岁月，不过Frank上个月刚认识他，所以这样说显得有点怪怪的。而第四家店Daring Double里的人们则是一群出了名吵闹的集会巫师，每当有新人到场他们都会欢呼，并举着热气腾腾的杯子欢快地高歌。
Frank在第五家店铺Exponentiated Expresso里找到了Billy。这是迄今为止大街上最喧闹、最俗气的咖啡馆，却凭借其含有三倍咖啡因的咖啡豆，成功招揽到了最忠实的粉丝们。生意好的日子里，每桌都会挤满絮絮叨叨的人，他们似乎认为一场愉快交谈的关键在于说话的音量。
今早，Exponentiated Expresso里的客人不那么喧闹，只有少数几张桌子有人，而其中大多数都是孤身一人的咖啡客，他们晃动着身体轻声哼唱。
Billy在中间的一张桌子坐下，扭曲着身子努力听着身旁的谈话。似乎没人注意到他。Frank在第一次扫视屋内时，甚至看漏了Billy。“Billy！”Frank叫道。
Billy怀有愧疚感地跳了起来。“Frank？”他咧嘴笑了起来，很高兴有人对他打招呼，然后又坐了回去，“拉把椅子过来呗。”“我正在找一些信息，”Frank一边解释，一边在Billy对面坐了下来。“说不准我有呢，”Billy说，“不过，最近我觉得有些事情想起来挺吃力的。”Billy说道，同时朝一个空了很久的杯子瞧着，估计并不是他的。
Frank示意咖啡师很快在桌上放了一杯啤酒。“记得任何有关警局失窃案的事吗？”Frank问Billy。
Billy睁大眼睛，畏缩了。“你是说……抢劫？”他心虚地问道。他的双眼扫视着屋内，但一如既往，并没人留意他。
Frank在桌上放了两枚金币，并努力让自己不要心疼这两枚金币。他花不起这钱，尤其当他不知道自己花钱买的是线索还是闲话时。但他清楚，让Billy提供信息不会便宜的。他俯身凑近一些：“前天晚上，”他悄然说道，“一大堆文件被贼偷走了。”“听起来不像是容易想起来的事情啊。”Billy说，他盯着金币，“恐怕你问错人了，Frank。”“这可是金子啊！”Frank咆哮道。“抱歉，我帮不到你。”Billy说，他再次环视一下屋内，然后补充道，“即便我知道一些关于失窃的事，我也会努力忘掉的。或许我知道一些小事，比如是谁帮忙运走了文件，但这不值得冒险，免得我睡醒一睁眼发现自己的鞋里塞满了牛粪。”
Frank瞪大了眼睛，但Billy沉默不语了。作为一个靠分享信息过活的人，Billy不肯透露这件事情的行为显得非常奇怪。“牛粪？”Frank问。
Billy点点头，但不再多说。“你就不能再具体点吗？”Frank问道，“是说北方或南方的牦牛吗？”“这重要吗？”Billy问，“问题在于，即使知道是谁安排的运输，我也不会记住的。如果那些人碰巧在镇外大约五英里处拥有一个大农场，在那儿可以轻易地让某人消失，那我就更不会记住了。而如果那座农场的主人有着非法活动的历史记录和危险的幽默感，那我就加倍更不会记住了。在这种情况下，记住任何事情都是绝对不明智的。”“太糟糕了，”Frank笑着说，“也许下次能记起来点。”他朝金币点点头，“希望它能让你将来能记住事儿。”
Frank起身，大步走出Exponentiated Expresso。他向左转，沿着街继续走。一走出三比特巷，他便可以兜回去，前往Crannock的农场——唯一与Billy的描述有点相似的农场。
在他经过第六家店Faulty Register时，他注意到一道影子钻进了附近的小巷。他压低嗓音骂了一句，但没有停步。Frank意识到自己被人跟踪了：看来警长上门找他时没有十分地谨慎。
但当他离开城里，踏上前往Crannock农场的粗糙泥土路时，发现自己的心情很好。Billy给他的并不多，但即便利用这一点点信息，也能看出使用高效搜索算法和使用穷举算法的不同。警用算法导论：穷举搜索
节选自Drecker教授讲义
用穷举搜索算法搜索目标值是要在整个搜索空间范围内尝试每一种可能性。最常见的穷举搜索是线性搜索，即按照顺序简单地检查所有不同的可能性。
想象一下，当你正在追逐强盗进入了一个废弃旅馆的二楼走廊时，接下来会发生什么？走廊里有30道门，全部是关闭的。如果你遵循正确的警方工作程序，你的同伴已经封锁了对面的楼梯，你和强盗被困在这层楼上，你将如何找到强盗？是随机选择一扇门打开，发现没有强盗，然后出来再随机打开一扇门，就这样跑来跑去，直到你幸运地找到了强盗？不！你应该搜索整个楼层，把所有的门依次踢开。
或者来思考一个算法，在一个数字列表（数组）中寻找一个目标值。线性搜索算法要从第一个数字开始查找，逐个地检查数字列表中的每一个值，直到找到目标值。假如我们要在一个数组中搜索5，那么搜索的过程如下：
线性搜索算法的优势是它们在任何领域都容易实现，即使要处理的是非结构化数据。你不必猜测强盗会在哪个房间，你只需要依次检查所有房间。穷举搜索算法的缺点是，在已经结构化的数据中采用这种搜索方式往往不够高效。如果你知道强盗在哪里，你可以使用这个情报来大大减少你踢开门的次数。
高效算法的关键在于有用的信息！3 罪犯农场里的数组和索引
Frank看到一匹警队的马正拴在Crannock先生的房子外，不禁大声爆了一句粗口。既然警长已经亲自上门来雇他了，怎么还会碰到其他的警官？如果警长不信任自己的警官们，或者是他们遭到了怀疑，警长就会把他们委派到城市边远地带去调查一些小案子。如果他们只是单纯的能力低下，也会落得同样的下场。但是，从现在的情况看，有人已经在调查这个案子，而且Frank已经落后了。
Frank从虚掩着的前门溜了进去，到门厅去听那位来调查的女警官和Crannock先生的谈话。Crannock先生厌恶地瞥了Frank一眼，不过Frank的出现似乎早在他预料之中。但是，那位女警官看起来倒有些措手不及。“你是谁？”她拿着羊皮纸和羽毛笔转向Frank问道。
Frank懒得理她。“Crannock先生，”他说，“再次见到你很高兴。”“你又来烦我们了，是吗？”Crannock说，“这里可不欢迎你。”“我才没指望你们欢迎我，”Frank答，“我是来找你妻子的，想问她几个小问题。”
那位女警官打量着他。“Frank？”她问，“Frank Runtime先生？前警探改行做私家侦探了？你在这做什么？谁的宠物龙走丢了吗？”她嘲笑道。
Frank还是没搭理她，说道：“Crannock先生，您的妻子究竟在哪？”
那个老男人举起了双手：“她啥都没干！她已经金盆洗手了，这次是真的。”这一幕演得算得上是业余演员了。
Frank笑了，他知道这话问得很令人不安，Crannock一定畏缩了。“我知道，Crannock先生，我是来向她请教专业知识的。要不我请这位警官接着和你聊……”“我是Notation警官。”那位年轻的女警官插嘴道，“我正在查案。”
她在撒谎，因为警官们永远都是和搭档一起调查案子的。更重要的是，Frank突然注意到她警徽上的名字是警长给他的执勤人员名单之中的一个，也就是说案发当晚，她也在警局值班。“Notation警官，”Frank说，“谁说我是来查案的了？说不定我只是来找一条走丢的龙呢！”
她皱了皱眉头。
屋后传来了一阵骚动，有人在叫Crannock，不过被一声响亮的马叫声打断了。“我的妻子正和那些马待在一块，”Crannock先生不耐烦地说，“行了，她在2号谷仓，快去吧，别再赖在我的房子里了！”Crannock把他们往前门赶，然后从后门急匆匆地跑了。“谢谢你！”Frank转身离开的时候喊道，“Crannock先生，见到您总是很愉快！”
Notation警官跟着Frank穿过了小花园，她很生气，每一步都重重地跺着地面，问道：“你知道你在往哪走吗？”“2号谷仓啊。”Frank回答。“我当然知道，”她咆哮道，“但2号谷仓在哪啊？”
Frank停下来转向她问道：“你是刚从警校毕业吗？Notation警官？”“什么？”“这样的搜索问题，只有菜鸟才会问。你没有上过警务程序课和数据结构课吗？或者是他们已经把这些课换成了小海龟画图这样不严谨规范的课程了？”
Notation愣了愣，说道：“我当然上过那些课啊，”她听起来有些底气不足，“但我的意思是……”
Frank打断了她：“那你就应该知道数组和索引。”“是的，不过……”Notation说。“在一个农场上找一个谷仓是一个再简单不过的搜索任务了，”Frank又打断了她，“我们可以用穷举的方法去搜索每一个建筑物。对农场上的每一个建筑都要检查一下是否为2号谷仓。在我上警校的那个年代，这是我们警用算法课第一节的内容。“但是我们现在可以做得更好。Crannock一家把六个谷仓排在了一条整齐的线上，就像是一个巨型数组。Crannock先生非常好心地为我们写好了谷仓的编号，也就是数组的索引，我们现在只需要走到对应的谷仓就行了。”“我不是想问这个！”Notation挥动着手臂大声吼道，“我知道怎么用数组里的索引，我也知道我们只用走到2号谷仓就好了，我毕业时在数据结构课和警用算法课上都拿到了第一，所以我不需要你在这给我说教如何正确使用数组。”“刚刚是你自己问的啊。”Frank回答道。“我问的是：你知不知道这个美丽可爱的谷仓数组在哪里？”“哦，原来你问的是这个啊，”他开始继续向前走，说道，“虽然你说你是第一名，但看起来仍像一个菜鸟。”“谷仓到底在哪？”Notation又一次吼着，仍然踩着重重的步伐赶上Frank。
Frank回头对她一笑：“这座小山上。”
他几年前得知，Crannock一家在生活中总是热爱运用数组的思想，近乎疯狂。他们会把所有的事物整理成井井有条的线性结构，然后将每个数组中的元素都标上清晰的索引。当Frank走过0号谷仓时，他看到了15个猪槽，每个猪槽可以放一份食物，农场里的喂猪人沿着猪槽摆放的直线，用勺子将猪食一份一份地送到这个数组的对应位置上。
Frank和Notation走到了2号谷仓，谷仓门口有个牌子标记着一个大大的“2”。相比之前遇到的人的态度，Crannock太太有些高冷的问候已经很令人欣慰了，至少她没有向他们砸任何东西……至少现在还没有。“你们想干什么？”Crannock太太问。“Crannock太太，”Notation担心Frank抢走了她的目击证人，抢先问道，“我能不能问你几个问题？”
Frank决定让Notation先问。Billy提供的线索只能指引他找到这个农场，但是Notation看起来收集了更多的信息。
Crannock太太冷笑一声，朝地上吐了口唾沫说道：“我啥都没干，我已经金盆洗手了。”“我不是来逮捕你的，”Notation说，“我想问你一些关于驴车——Array Cart（数组车）的问题。”
Frank心里闪过一丝疑惑。Notation难道是为了调查另一个案子才来这里的吗？他有些怀疑。直觉告诉他这个女人是为了那些丢失的文件而来的，而且他很相信自己的直觉。“Array Cart啊，”Crannock太太说道，虽然她表面上是毫不遮掩的傲慢，但是语气里还是夹杂着疑虑，“这是我的发明，基于数组的原理而创造的。它有很多分开的棚，用来存放我的动物们。每一个棚只能存放一只动物。我可以直接把某一只动物放出来或者关进去，因为每个棚都有一扇门。这样可以直接地访问每一个存储位置，既方便又节约时间。”“这方法确实很巧妙，”Notation承认道，“你把数组和索引的概念运用在了牲畜的转移上。”“这只是一个开始，”Crannock太太补充说，“我和一个巫师在研究一种新型Array Cart，新型的Array Cart上带有魔法指针！我敢打赌它们作为警队的装备是再好不过的了。跟你的警长说我可以给他一点折扣。”
Frank不得不赞扬Notation的机智，一旦说到数组，Crannock家的人就开始喋喋不休了。“你现在是不是租出去了几辆Array Cart？”Notation试探道。
Crannock太太突然变得极其冷漠地说：“我们做的事没有违法，我们交了税。”
Frank差点笑出声，但还是忍住了。“两天前的晚上你是不是恰好把某些Array Cart租给了别人？”Notation步步紧逼地问道，“一种小一点的只有六个棚的Array Cart？”“有可能吧。”Crannock太太说。她冷漠的举止渐渐转变为敌意。
Notation问：“你有记录是租给谁了吗？”“没，”Crannock太太说，“一旦借的人把Array Cart还回来，我就会把记录撕掉，我现在也想不起来谁借的那一辆了。”
Billy的暗示似乎已经得到了验证。一个想逃跑的罪犯能租到Array Cart的地方不多，租完Array Cart就被忘记更是不太可能，Crannock太太虽说自己已经金盆洗手，但她很明显地在向从前的同伙提供非常有价值的帮助。“你确定你一点都不记得之前的客户了吗？”Notation不罢休地问道，但是Frank知道这个问题是没有意义的。他曾经为了一头被偷的牦牛而问过她三个小时，尽管她是被偷的一方，但她还是没有告诉他任何信息。Crannock太太不愿意开口。
Notation在尝试几种不同的问法，希望套出一点话，这时Frank悄悄地从谷仓溜了出去，找到了Array Cart的停车场。
不出他所料，停车场的十个车位被整理成了标过号码的数组，只有2号、4号和8号车位停着Array Cart。不过2号和4号的车位上停的都是有10个棚的Array Cart，都不是Notation说的那种。8号车位上停的才是有6个棚的Array Cart，它的轮子上还留着没完全干的泥土。
Frank扫视了周围，跳进这个有六个棚的Array Cart上。Array Cart的地板上零散地铺着稻草，但没有牲畜。Frank逐一打开每一个棚的门，在空无一物的空间里寻找线索。他趴在地上，一层层拨开稻草，直到找到了一些羊皮纸的碎片。
Frank一共找到了六片，可能是在把文件搬下Array Cart时被钉子割下来的边边角角。其中只有两片有文字，看起来像是账目的一部分。虽然这不是什么可靠的线索，但这能表示这辆Array Cart和案子脱不了干系。
Frank开始检查Array Cart的前面，小心地在驾驶座找线索。他在椅子那里找到了第一条真正的线索——在木椅子残破的地方，卡着几根黑色和橙色的细线，是披风上的线。Frank断定这件披风一定是新的，因为细线还没褪色。他心满意足地把细线装在口袋里，从Array Cart上跳下来。
当呼吸到一口新鲜空气时他才意识到，原来自己一直是屏住呼吸的。Array Cart的周围弥漫着鱼腐烂后的腥臭味。他嗅了嗅，循着臭气找到了根源——被泥土盖住的轮子。他深吸了一口气，但是立马就后悔了，那些泥土散发出的鳗鱼腐臭的气味是如此恶心。
Frank一边微笑一边作呕地远离了这辆Array Cart，因为虽然他不知道是谁租了这辆Array Cart，但他毫无疑问地知道了这辆Array Cart曾经去过哪里。警用算法导论：数组
节选自Drecker教授讲义
数组是可以让你存储多个值的简单数据结构。一个数组就像一排箱子一样，每个箱子可以存储一条信息，例如一个数或一个字符。
数组结构的意义在于，可以通过指定一个位置或索引的方法来存储或读取数组中的任何值（或元素）。很多编程语言数组的索引都是从0开始的。这也就意味着第1个值存放在第0位，第2个值存放在第1位，以此类推。通常数组A中索引为i的值存储在A[i]中。例如，上面的数组A的第3个元素的索引为2，我们用A[2]表示，存储的值为19。
昨天警校组织大家参观监狱时你可能已经发现了这个结构的运用。国王亲自建议使用索引来对牢房进行编号，这样可以简化对犯人的检索。现在每个警局都根据当地犯人的人数配备了4～8个编过号的数组牢房来关押犯人。4 字符串及隐藏的信息
Frank甩掉Notation警官后从农场后门离开，那里有一块很大的指示牌正朝着马路。多年来，Crannock夫妇一直使用这个指示牌来传播各种加了密的非法活动的消息。这些天，对于前来此处的罪犯而言，它堪称一个旅游景点——在这里，恶棍领着年轻的门徒，聚在一起追忆那些以“想当年……”开头的故事。
指示牌是一个AnyText模型。它可容纳三排字符数组，每排有12个空位，每个字母、空格或标点符号都需要占用一个空位。这意味着指示牌可以容下36个字符——足以显示一个完整的非法活动通知。每周一早晨，Crannock夫妇中的一人就会拖着一筐字母到指示牌前，然后逐个将对应的字符放入至数组的每个空位中。
Frank在当警察的第一个星期里，他的搭档就带他出去“检查指示牌”。当时的消息是“APPLE PICKER WANTED”和“GOT SLUGS？”，对Frank来说，这两则消息看起来貌似无关紧要。Crannock夫妇是在寻找一名采摘工来帮助采摘苹果，同时问是否有需要帮忙除去家里的鼻涕虫的。当Frank对他的搭档（一位从业20年的老警察）说这事时，她笑了。“他们就是希望你这样理解，”Rossile警探解释道，“你得看懂其中暗含的意思，搞清楚罪犯想的是什么。在本案中，招聘苹果采摘工是指他们在试图招募一名小偷。其实就是愿意从手推车或类似车辆上偷苹果的人。”“那鼻涕虫呢？”Frank问道。“非法鼻涕虫赛跑，”她回答道，“他们每隔几个月都会在这里举行比赛。到时候你就会明白的。”
就这样，Frank学会了每周检查Crannock夫妇的指示牌，以便了解罪犯的世界。开始的几个月过后，他已经学会解读大部分密码了。农夫（farmhand）就是指追随者，通过增加修饰语可以表达需要什么样的追随者，例如很强壮、很残酷，或是具体的人数。印刷艺术家（print artist）是指造假者，而声乐艺术家（vocal artist）则是指骗子，诸如此类。一群小鸡（a flock of chickens）这个词语把Frank难住了好几天，最后，Rossile警探将此解读为：需要一群头脑简单四肢发达的热血青年到处乱跑并制造出噪声，以此来分散人们的注意力。
在当警察第一年快结束的时候，Frank已经成为解读指示牌的高手了。过去几年里，Frank通过指示牌解读罪犯消息时，唯一一次感到棘手的是他的王国都遭遇了巫师Exponentious发出的攻击那次。巫师Exponentious对王国中所有用数组设计的指示牌上都施了咒语。咒语改变了原有数组的索引方式，这导致Crannock夫人放置的字母位置都是错的。整整一个星期，Crannock夫妇家的指示牌都被认为是毫无用处的信息。
由于咒语仅仅是将原有的字母顺序打乱，而且AnyText模型是利用三个单独数组实现的，所以Frank可以逐一对每行进行破解。最终他解开了密码：招募防御巫师（DEFENSIVE WIZARDWANTED）。
但是，今天的消息显得太直白了。事实上，这是他在Crannock夫妇家的指示牌上见过的最狡猾的消息。指示牌上面写着“ARRAYCARTS FORRENT”和“NO QUESTIONS”。警用算法导论：字符串
节选自Drecker教授讲义
数组不仅可以存储一列数字，它们还可用于存储由一列字母组成的字符串。许多编程语言也都是利用数组来实现字符串的存储的，数组中的每一位都可容纳一个字符，这个字符可以是字母、数字、符号或空格。与使用其他数据类型的数组一样，字符串中的某一个字符也可直接通过数组的索引来访问。
在你的警队生涯中，你会逐渐掌握使用数组来存储文字信息的方式。所有的标准警用表格都要求警官能在每页的顶部用一个32位的数组记录他们的姓名。通常一个月以后，你就已经用此方法填满400个这样的数组了。5 对一艘走私船的二分搜索
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 这看起来并不是很多的信息，但是它足够让我们的搜索更加高效。 二分搜索算法的工作原理是：不断地将搜索空间分成两半，并且把搜索空间限制在其中的一半中。这个算法通过改变上下界限有效地限制了搜索空间。上界（IndexHigh）标记了搜索空间有效数组中最高的索引，下界（IndexLow）标记了搜索空间有效数组中最低的索引。通过这个算法，如果目标值在这个数组中，就可以保证： 在搜索的每一步中，我们只需依次判定上界和下界中间的值： 接下来，我们将中间值A[IndexMid]和目标值v进行比较。如果中间值小于目标值（A[IndexMid] 如果中间值比目标值大（A[IndexMid]>v），我们就知道目标一定位于中间值之前，于是我们将IndexHigh改为IndexMid-1来使得搜索空间变成原来的一半。 当然，如果我们发现A[IndexMid]等于v，我们可以直接结束搜索，找到目标值。 现在我们就来使用二分搜索在下面这个已排序的数组中寻找到15。虚线框出的方块是算法当前需要判定的值，而被阴影遮住的部分则是在搜索中被排除的部分。 第一个被判定的中点的值是11，比我们的目标值15小。因为我们知道这个数组是按照升序排列的，所以可以排除中点及其之前的所有部分。我们将下界索引移动到适当的地方（IndexLow=IndexMid+1）。 在第二次比较之后，我们发现中点值是52，比目标值大。我们可以排除中点和它之后的所有部分。此时需要移动我们上界（IndexHigh=IndexMid-1）。 请注意，通过这几次的操作，此时虽然下界已经是目标值了（v=15），但是我们仍需要继续搜索，直到中间值指向目标值。这是因为二分搜索是对中间值进行判定，而不会判定上界和下界是否是目标值。 如果目标值不在数组中会发生什么呢？在搜索过程中，上下界之间的距离会越来越近，直到它们之间没有任何还未检查过的值。因为我们总是将其中一个界限移动到中间值的另一边，所以我们可以在IndexHigh<Indexlow的时候停下来，这个时候就可以保证目标值不在数组中了。
试读结束[说明：试读内容隐藏了图片]