基本思路
把目标值与列表的第一个值比较。如果相等,就停止:目标值在第 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 — 无需安装,无需信用卡即可启动。
试试线性搜索