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

译　者　序

算法！Algorithms！

咳咳！很多人一听到这个词，估计脑袋就要炸了：一定又是复杂极了的东西，看来此书必定翻不过节，就要睡着了。

没错，很多算法书虽然写得很精妙，但凭我这种智商一口气多只能看5到10 页，就会乖乖滚回去睡觉了。不少读者说《啊哈！算法》一口气能读100页，这已经是极限。那么，这本《啊哈！算法神探：一部谷歌首席工程师写的CS小说》或许可以一口气读完，没错，是读完！

整本书巧妙地将算法穿插入一场离奇的盗窃案的侦破中。没有一行代码和公式，取而代之是一场又一场鲜活的破案游戏，带你游走在各个犯罪现场，让你身临其境地观察我们的主人公是如何使用算法搜寻线索并逐步揭开事实真相的。虽然这本书并不是教科书，但通过这种轻松的阅读学习，你可以对算法的本质有大致了解。在酣畅淋漓地读完本书之后，再去翻阅其他算法书籍，你会惊奇地发现，自己竟然可以看懂那些枯燥苦涩的代码和公式了。

其实，在阅读本书之前，你甚至不需要掌握任何编程的基础知识。这并不影响你阅读全书，并以轻松有趣的方式了解这些算法。

然而，时间紧张加之我们翻译水平有限，请恕不能将原作者的精巧行文完美地展现在你面前。译文中难免有不足和疏漏之处，还请不吝批评指正。翻译期间得到了不少朋友的帮助，在此向他们表示感谢。特别感谢我的挚友丁广浩，他目前就职于美国的Amazon。在 On-Call Duty 的日子里面，他还抽时间帮我解答疑问，甚是感激。另外，也非常感谢武汉外国语学校的张竞文同学和浙江大学的陈泓宇同学。

好嘞，故事要开始了，让我们跟随Frank探长和Notation警官一起走入这场奇妙之旅。

啊哈磊

《啊哈！算法神探：一部谷歌首席工程师写的CS小说》围绕程序设计典型算法，精心编织了一个场景，让读者通过本书学会优先搜索、深度优先搜索、迭代加深、并行算法、二分搜索等算法背后的原理，字符串、数组、栈和队列等基本计算机科学概念，学习如何修改搜索算法以适应不同的数据结构、如何在特定情况下选择的算法，以及何时应该使用基于常识的启发式算法，以加深对程序世界的理解。 本书的每一章都会伴随情节引入一个新的算法概念，并在结尾处回顾总结本章内出现的专业知识。

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

译者简介：

啊哈磊（纪磊）
啊哈编程创始人，曾经的编程算法竞赛保送生，毕业于武汉大学。曾在微软亚洲研究院从事机器学习相关研发工作，也做过老师，是全国青少年信息学奥林匹克竞赛金牌教练。著有畅销编程科普书《啊哈C语言！逻辑的挑战》等，总计销量超过二十万册。

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

章　搜索问题 1 

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

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

第二章　穷举搜索寻线人 7 

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

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

第三章　罪犯农场里的数组和索引 15 

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

警用算法导论：数组 22 

第四章　字符串及隐藏的信息 23 

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

警用算法导论：字符串 26 

第五章　对一艘走私船的二分搜索 27 

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

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

第六章　二分搜索寻线索 37 

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

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

第七章　调整算法，大胆逃离 45 

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

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

第八章　Socks：一个突如其来的插曲 55 

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

第九章　倒退一步，继续搜索 63 

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

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

第十章　用广度优先搜索去开锁 69 

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

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

第十一章　废弃监狱中的深度优先搜索 81 

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

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

第十二章　餐厅中的栈和队列 91 

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

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

第十三章　用栈和队列搜索 101 

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

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

第十四章　分头行动——并行搜索 109 

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

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

第十五章　迭代加深可以救你的命 117 

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

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

第十六章　逆向索引：缩小搜索范围 127 

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

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

第十七章　二叉搜索树陷阱 135 

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

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

第十八章　建造二叉搜索梯 145 

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

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

第十九章　疑犯的二叉搜索树 151 

搜索第七站：调查调职记录，Frank让Socks生成巨大的闪闪发光的魔法树，但是没能找到任何可疑之处。 

警用算法导论：二叉搜索树Ⅲ 160 

第二十章　将疑犯加到搜索树中 163 

Frank决定带着魔法树去见警长，不过途中他们停在了警局记录处，他们需要向魔法树中增加一些节点。 

警用算法导论：二叉搜索树Ⅳ 169 

第二十一章　二叉搜索树的属性 171 

在增加节点的过程中，Socks犯了“小”错误，这引起了Frank的抱怨、咒骂和怀疑。 

警用算法导论：二叉搜索树Ⅴ 173 

第二十二章　公文字典树 175 

途中他们又来到警局档案室，Frank得以在事故现场侦察，在这里他找到了新的线索。 

警用算法导论：trie树 179 

第二十三章　优先搜索：侦探值得信赖的工具 183 

Frank与警长交谈，发现事态比想象中的更紧迫而严重：攻击城堡的计划、强大的魔法面具、危险的邪恶巫师联盟…… 

警用算法导论：优先搜索 190 

第二十四章　用优先队列进行调查 193 

Notation受到警长严厉批评，被停职，因为她一直在擅自调查不属于自己的案件。 

警用算法导论：优先队列 199 

第二十五章　用优先队列来解锁 201 

Frank想回到自己的办公室，却发现再次被跟踪了，他甩掉探子，巧妙地解开安全屋的密码，躲进了安全屋。 

警用算法导论：数据结构和搜索 205 

第二十六章　启发式搜索 207 

搜索第八站：安全屋里的静心反思。Frank反复研究着找到的所有线索，忽然他开始怀疑之前的所有推断。可靠的线索用尽了，模糊的线索也没有了…… 

警用算法导论：启发式搜索 210 

第二十七章　警察学院中的“堆” 213 

Loop教授的回忆：警察学院基于教龄分配办公室，95岁的Loop教授有长达70年的教龄，终于争夺到了本应属于自己的办公室。 

警用算法导论：堆 219 

第二十八章　搜索难题 223 

搜索第九站：Frank向Loop教授请教咒语知识。巫术犯罪学是一个危险的领域，而Loop教授却一直能够幸存下来。在这里Frank终于厘清了线索。 

警用算法导论：期末考试复习课 229 

第二十九章　搜索终点站 231 

Frank与Notation来到警局的监狱，一举抓获戴着魔法面具、试图解救自己首领的小巫师，没错，他就是一路同行的Socks。 

结　　语 239

《啊哈！算法神探：一部谷歌首席工程师写的CS小说》围绕程序设计典型算法，精心编织了一个场景，让读者通过本书学会优先搜索、深度优先搜索、迭代加深、并行算法、二分搜索等算法背后的原理，字符串、数组、栈和队列等基本计算机科学概念，学习如何修改搜索算法以适应不同的数据结构、如何在特定情况下选择的算法，以及何时应该使用基于常识的启发式算法，以加深对程序世界的理解。 本书的每一章都会伴随情节引入一个新的算法概念，并在结尾处回顾总结本章内出现的专业知识。

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

译者简介：

啊哈磊（纪磊）
啊哈编程创始人，曾经的编程算法竞赛保送生，毕业于武汉大学。曾在微软亚洲研究院从事机器学习相关研发工作，也做过老师，是全国青少年信息学奥林匹克竞赛金牌教练。著有畅销编程科普书《啊哈C语言！逻辑的挑战》等，总计销量超过二十万册。

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