算法神探：一部谷歌首席工程师写的CS小说

本书围绕程序设计典型算法，精心编织了一个扣人心弦又趣味横生的侦探缉凶故事。小说主人公运用高超的搜索技巧和精深的算法知识，*终识破阴谋、缉拿元凶。其间，用二分搜索搜查走私船、用搜索树跟踪间谍、用深度优先搜索逃离监狱、用优先队列开锁及用*佳优先搜索追寻线索等跌宕起伏又富含算法精要的情节，让读者在愉悦的沉浸式体验中快速提升境界，加深对程序世界的理解。本书适合开发人员、编程爱好者和相关专业学生阅读，也是少儿计算机科学启蒙的**读物。

Jeremy Kubica 在 Google 任职首席工程师，着力于机器学习和算法方向。他拥有康奈尔大学的计算机科学本科学位和卡耐基梅隆大学的机器人专业博士学位。在研究生期间，他设计了一个算法，可以探测对地球有威胁的小行星（当然，还尚未能阻止那些小行星）。Kubica 同时也是著名博客Computational Fairy Tales的作者。

关于技术审校者

Heidi Newton 拥有新西兰坎特伯雷大学计算机科学专业的学士学位，以及新西兰惠灵顿维多利亚大学计算机科学专业的硕士学位。她目前就职于坎特伯雷大学计算机专业的代码复仇者研究小组，并在业余时间进行相关辅导和咨询工作。她目前致力于改善关于计算机科学和编程的教学资源。

译者介绍

啊哈磊：原名纪磊，毕业于武汉大学。曾在微软亚洲研究院研发“爬虫”，全国青少年信息学奥林匹克金牌教练。著有《啊哈C语言！逻辑的挑战》和《啊哈！算法》系列编程科普丛书，并被引进至港澳台。

李嘉浩：曾获全国青少年信息学奥林匹克竞赛金牌，国家集训队*小选手。现就读于美国麻省理工学院计算机科学及音乐双专业。喜欢行走在科学与艺术的交接点。

无论你是计算机科学的学生还是业余爱好者，本书都是能让你在引人入胜的情节中学习算法知识的完美选择。Frank是一位被解雇的前探员，老练的私家侦探和搜索专家。追寻他的足迹，你会学到：

◎*佳优先搜索、深度优先搜索、迭代加深、并行算法、二分搜索等算法背后的原理

◎字符串、数组、栈和队列等基本计算机科学概念

◎如何修改搜索算法以适应不同的数据结构

◎如何在特定情况下选择*适合的算法，以及何时应该使用基于常识的启发式算法

译　者　序

算法！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 Lipovacˇa为本书提供了精美的插图。这些插图很好地刻画了本书的人物特色和故事情节。

感谢 Heidi Newton从专业角度进行的细致深度的审校。她的审阅很大程度上确保了本书所涵盖的内容和概念能够以准确易懂的方式呈现出来。非常感谢她针对书中的晦涩难懂处给予的提醒。

同时也感谢所有阅读过本书早期手稿并提供了宝贵建议的人：John Bull、Mike Hochberg、Edith Kubica、Regan Lee和 Kristen “Kit” Subbs 博士。感谢 Ilana Schwarcz 对于本书早期手稿的编辑，以及对本书在行文上的建议和帮助。

最后，我想由衷地感谢我的家人，特别是父母在我孩童时期对于我的计算机兴趣的支持，以及对我写作本书给予的鼓励。

导　　读

本书关注的是计算机思维和搜索算法。这些故事介绍并阐释了较高层次的计算机思想，探索了它们背后的动机及其在非计算机领域中的应用。本书并不奢望对算法进行非常详尽而全面的描述，书中的故事也不是为了替代计算机科学中那些坚实而严谨的技术性描述。相反，它们的作用更像是插图：对整体思想进行补充，帮助你更好地理解算法。

本书介绍了一系列的计算方法，它们大致上属于搜索算法的范畴。书中每一章首先通过一个故事来讲解算法的大致思想，随后再用讲义的形式来对算法进行更为技术性的解释。读者可以完全跳过这些技术讲解部分，同时又不会错过任何一个精彩的故事。

本书假定你已经对一些基本的计算机科学思想有所了解，但你并不需要掌握任何一门编程语言。本书中的算法适用于各种编程语言和不同领域的问题。

1 　搜索问题............................................................................................................ ......1

警局档案室里的几百份卷宗莫名失踪，警长求助Frank，一位几年前被自己亲自辞退的前警官。

警用算法导论：搜索问题....................................................6

2 　穷举搜索寻线人......................................................... .................. .................. ......7

搜索第一站：Frank寻找“玻璃箱”Billy。作为一个靠分享信息过活的人，Billy这次竟然不愿透露信息。

警用算法导论：穷举搜索....................................................13

3 　罪犯农场里的数组和索引....................................................................................15

搜索第二站：Frank在Crannock农场偶遇Notation警官。虽然饱受Crannock夫妇的呵斥，Frank还是幸运地在数组车上找到一根珍贵的线头。

警用算法导论：数组....................................................... 22

4 　字符串及隐藏的信息...........................................................................................23

Frank的回忆：初入警局时学习辨识Crannock农场的指示牌信息，这个指示牌被用来传播各种加了密的非法活动消息。

警用算法导论：字符串..................................................... 26

5 　对一艘走私船的二分搜索....................................................................................27

搜索第三站：Frank和Notation来到Usb港，根据船只的到港时间快速锁定走私船Retry Loop号。

警用算法导论：二分搜索Ⅰ.................................................. 33

6 　二分搜索寻线索.....................................................................................................37

Frank和Notation假装食品监察员闯入Retry Loop号，快速翻看造假日志寻找蛛丝马迹。

警用算法导论：二分搜索Ⅱ............................................................................43

7 　调整算法，大胆逃离.............................................................................................45

他们被船上恶棍们拖上甲板，恶棍们的资历是如此浅，以至于什么信息都套不出来。

警用算法导论：改编你的二分搜索法.........................................54

8 　Socks：一个突如其来的插曲...............................................................................55

峰回路转，素不相识的小巫师Socks来营救，营救武器竟然是一桶桶的腌鳗鱼。

9 　倒退一步，继续搜索............................................................................................63

搜索第四站：Mudwall港口，与村民们再三确认，最近没有船到港，一无所获地离开。

警用算法导论：倒退一步....................................................67

10 　用广度优先搜索去开锁......................................................................................69

搜索第五站：Frayed Cable岛，这里有一座废弃的监狱，Socks用咒语打开了监狱大门的锁。

警用算法导论：广度优先搜索................................................ 76

11 　废弃监狱中的深度优先搜索.............................................................................81

这座废弃的监狱像迷宫一样，不过在Frank的带领下，他们真的在这里找到了那些失踪的卷宗！然而……

警用算法导论：深度优先搜索................................................ 89

12 　餐厅中的栈和队列.............................................................................................91

Frank的回忆：在警察学院的最初两个月，Frank在餐厅打工，在一次偶然聊天中他意识到了数据结构的重要性。

警用算法导论：栈和队列Ⅰ..................................................97

13 　用栈和队列搜索................................................................................................101

废弃监狱里房间的门突然关闭，卷宗被燃烧，重要线索被毁，他们落荒而逃。

警用算法导论：栈和队列Ⅱ.................................................106

14 　分头行动——并行搜索...................................................................................109

返回Usb港的途中，Frank决定上岸后将Notation和Socks支开，因为他感觉自己无法相信任何人。

警用算法导论：并行算法...................................................115

15 　迭代加深可以救你的命...................................................................................117

Mavis的回忆：在自己还是学徒的一次出海中，虽然地图丢失了，他们仍然用一种看似笨拙的方法在茫茫大海中找到了补给站。

警用算法导论：迭代加深...................................................125

16 　逆向索引：缩小搜索范围.................................................................................127

搜索第六站：上岸后Frank拿着在Crannock农场找到的线头去请教披风专家Cloaksworth 先生，确认这是一件被施了咒语的警察披风上的线头。

警用算法导论：逆向索引...................................................132

17 　二叉搜索树陷阱................................................................................................135

谢过Cloaksworth先生后Frank走在街上，发现自己被探子跟踪了。他转而去追探子，被引入了下水道内建造的高高的二叉搜索梯。

警用算法导论：二叉搜索树Ⅰ...............................................142

18 　建造二叉搜索梯................................................................................................145

Frank一层层爬下梯子，然而爬到最后一层时他受伤了。探子放铁蛇来围攻，Frank艰难爬回地面。

警用算法导论：二叉搜索树Ⅱ...............................................150

19 　疑犯的二叉搜索树 ..........................................................................