线性搜索

在一份未排序的名单上找一个名字时,你做的就是线性搜索:从顶部开始往下读,直到找到为止。它是最简单的搜索方法,适用于任何列表,对于短列表通常也就够用了。

列表中的柱子从头开始逐个检查,已检查的柱子变淡,一条虚线标出目标值的高度,匹配的柱子高亮显示
列表中的柱子从头开始逐个检查,已检查的柱子变淡,一条虚线标出目标值的高度,匹配的柱子高亮显示

基本思路

把目标值与列表的第一个值比较。如果相等,就停止:目标值在第 1 位。否则与第二个值比较,然后第三个,依此类推。如果最后一个值也不匹配,目标值就不在列表中。无需预先了解列表:它不必有序,值可以是任何能比较是否相等的东西。

示例

在 5, 1, 4, 2, 8 中查找 4。5 等于 4 吗?不。1 呢?不。4 呢?是:经过 3 次比较,在第 3 位找到。再在同一列表中查找 7。五个值逐一检查,没有一个匹配,所以经过 5 次比较,得出 7 不在列表中。

比较次数

找到第 k 位的值需要 k 次比较。如果目标值在每个位置的可能性相同,平均需要 (n + 1)/2 次比较:40 个值时为 20.5 次。不存在的值总要 n 次,因为只有在最后一次比较之后,才能确定没有值匹配。所以代价与列表长度成正比,记作 O(n)。

更快的搜索需要有序

线性搜索不能跳过任何值,因为在未排序的列表中,任何值都可能在任何位置。列表一旦有序,一次比较告诉你的就不只是相等与否:它还告诉你目标值在哪一侧。二分查找利用这一点每步把列表减半,约需 log₂ n 次比较,40 个值时最多 6 次。不过排序也要花时间,所以对于只查找一次的列表,线性搜索往往是更好的选择。

小改进

哨兵版本在搜索前把目标值放到列表末尾,这样循环只需检查是否匹配,而不必同时检查是否到达末尾。每次找到一个值时把它向前移一位或移到最前面,可以让经常查找的值随着时间推移越来越快找到。这两种方法都不会改变最坏情况下的 n 次比较。

动手试试

打开应用,在“查找”中选择一个值,然后按“单步”。虚线显示目标值的高度,每个值在检查时高亮,被排除后变淡,匹配的值变成绿色。查找一个不在列表中的值,可以看到完整检查一遍的过程;或者关闭“找到第一个匹配就停止”,并选用少量不同值,找出多个匹配。

常见问题

线性搜索的时间复杂度是多少?

最坏和平均情况下为 O(n),最好情况下为 O(1),即目标值是第一个值时。它不需要额外内存。

线性搜索和二分查找有什么区别?

线性搜索按顺序检查每个值,适用于任何列表。二分查找只适用于有序列表,但它每步都把可能包含目标值的部分减半,所以约需 log₂ n 次比较,而不是最多 n 次。

线性搜索需要有序列表吗?

不需要。这正是它的主要优点。在有序列表上,一旦越过目标值应在的位置,它就可以停止,但仍比二分查找慢。

线性搜索用在哪里?

凡是列表很短或未排序的地方:在小数组中查找元素,扫描只能按顺序读取的文件或数据流,或检查每个元素是否满足某个条件。许多库函数,比如 JavaScript 的 indexOf 和 Python 的 list.index,都是线性搜索。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

试试线性搜索