撰文/张飞（清华大学终身学习实验室课程设计主管）

很多人已经会熟练使用互联网搜索引擎了。但是，大家真的理解搜索引擎背后的算法吗?互联网上那么多的信息，搜索引擎是怎样快速定位找到内容的呢?

其实，在大量的数据中搜索的时候，搜索引擎需要用到一些巧妙的方法来加速搜索的过程。这里通过常见的“大海战”游戏，介绍三种常用的数据搜索算法：线性 ( sequential ) 搜索算法、二分( binary ) 搜索算法，还有散列 ( hashing ) 搜索算法。

大海战游戏的目标，是用最少的炮弹击中敌方的军舰：游戏开始时，参战的两位“船长”各自选择一艘自己的战船作为“旗舰”，告诉对手旗舰上的编码(对方看不见编码);两人轮流猜测军舰所在的位置，每猜测一次，计炮弹发射一次;用最少数量的导弹击中对方旗舰(“搜索”到军舰位置)者获胜。

☆ 线性算法

线性算法也叫顺序算法，是一种最简单的算法。当搜索的数据量不大，数据本身很简单又排列无序的时候，它不失为一个有效的方法。

具体来说，线性算法要做的就是逐一比对数据——既然是无序的数字，那就没有什么好想的，一个个猜呗，看看运气好不好。它是最简单、最低效、最没有什么“算法”的算法。

采用线性算法时，假设参战的双方各有n艘战舰的话，搜中敌舰所需的次数是1~n次。

☆二分法

假设双方战舰已经根据编码大小顺序排列好，且在每次猜测时，对方会反馈你的猜测是“大了”还是“小了”。

如何快速定位旗舰呢?不如试试“二分法”。

这种算法用于已排序数据，每次取中间值查询——就算没有猜中，每次也能排除掉一半的错误答案。

二分法的神奇之处在于：即使数据总量翻了一倍，我们也只需要多加一次查询。当数据量不断翻倍的时候，二分法的魔力就凸显得更明显——就算有1000艘敌舰，也只需不到10次猜测就可命中。

☆ 散列法

假设参战双方每艘船编码的各位数字之和，尾数与其所在的列数相同(例如第2列的船编码为20、57、138、444)，其他的游戏规则还是和之前一样。我们需要几次才能击中敌舰呢?取决于每列最多有几艘船。

像这样，把搜索的数据按照一定方法，换算成便于查找的关键字、很快定位到一个小范围，再在小范围内去查找的方法，叫做“散列法”。该算法会将所有的关键字组成“关键字表”，并按照关键字表分组数据。如此一来，在实际查找时就可以快速定位到数据所在组，并在组内进一步查询。

其实，我们可能在不知不觉中用到过散列法。翻看微信里的联系人列表时，通过右侧的首字母，就可以快速定位到姓氏拼音的位置;在这个首字母里去寻找，就非常快了。

说到底，线性算法、二分法和散列法，哪一种最快呢?实际生活中，散列法一般是最快的一种方法。但是如果分组方法不够好，在同一列里有太多的数据，散列法就很低效了。所以我们面对不同的数据时，需要通过具体分析找到最合适的搜索方法!