不插电编程课3:搜索算法
撰文/张飞(清华大学终身学习实验室课程设计主管)
很多人已经会熟练使用互联网搜索引擎了。但是,大家真的理解搜索引擎背后的算法吗?互联网上那么多的信息,搜索引擎是怎样快速定位找到内容的呢?
其实,在大量的数据中搜索的时候,搜索引擎需要用到一些巧妙的方法来加速搜索的过程。这里通过常见的“大海战”游戏,介绍三种常用的数据搜索算法:线性 ( sequential ) 搜索算法、二分( binary ) 搜索算法,还有散列 ( hashing ) 搜索算法。
大海战游戏的目标,是用最少的炮弹击中敌方的军舰:游戏开始时,参战的两位“船长”各自选择一艘自己的战船作为“旗舰”,告诉对手旗舰上的编码(对方看不见编码);两人轮流猜测军舰所在的位置,每猜测一次,计炮弹发射一次;用最少数量的导弹击中对方旗舰(“搜索”到军舰位置)者获胜。
☆ 线性算法
线性算法也叫顺序算法,是一种最简单的算法。当搜索的数据量不大,数据本身很简单又排列无序的时候,它不失为一个有效的方法。
具体来说,线性算法要做的就是逐一比对数据——既然是无序的数字,那就没有什么好想的,一个个猜呗,看看运气好不好。它是最简单、最低效、最没有什么“算法”的算法。
采用线性算法时,假设参战的双方各有n艘战舰的话,搜中敌舰所需的次数是1~n次。
☆二分法
假设双方战舰已经根据编码大小顺序排列好,且在每次猜测时,对方会反馈你的猜测是“大了”还是“小了”。
如何快速定位旗舰呢?不如试试“二分法”。
这种算法用于已排序数据,每次取中间值查询——就算没有猜中,每次也能排除掉一半的错误答案。
二分法的神奇之处在于:即使数据总量翻了一倍,我们也只需要多加一次查询。当数据量不断翻倍的时候,二分法的魔力就凸显得更明显——就算有1000艘敌舰,也只需不到10次猜测就可命中。
☆ 散列法
假设参战双方每艘船编码的各位数字之和,尾数与其所在的列数相同(例如第2列的船编码为20、57、138、444),其他的游戏规则还是和之前一样。我们需要几次才能击中敌舰呢?取决于每列最多有几艘船。
像这样,把搜索的数据按照一定方法,换算成便于查找的关键字、很快定位到一个小范围,再在小范围内去查找的方法,叫做“散列法”。该算法会将所有的关键字组成“关键字表”,并按照关键字表分组数据。如此一来,在实际查找时就可以快速定位到数据所在组,并在组内进一步查询。
其实,我们可能在不知不觉中用到过散列法。翻看微信里的联系人列表时,通过右侧的首字母,就可以快速定位到姓氏拼音的位置;在这个首字母里去寻找,就非常快了。
说到底,线性算法、二分法和散列法,哪一种最快呢?实际生活中,散列法一般是最快的一种方法。但是如果分组方法不够好,在同一列里有太多的数据,散列法就很低效了。所以我们面对不同的数据时,需要通过具体分析找到最合适的搜索方法!