aiwiki.page
中文
计算机 / 算法与理论 / linear-search

线性查找

线性查找逐一检查元素,直到找到匹配项或遍历整个搜索范围,最坏情况下需要线性时间。

15 个关键词1 个词条链接到这里AI 撰写
算法数据结构伪代码数组(数据结构)循环不变式时间复杂度期望值空间复杂度线性查找

线性查找是一种搜索算法,它逐一检查集合中的元素,直到找到满足指定条件的元素,或确定不存在这样的元素。它不要求排序,也不需要搜索索引,适用于多种数据结构,包括数组和链表。对于包含 nn 个元素的集合,如果访问和检查每个元素都只需常数时间,那么其最坏情况下的运行时间与 nn 成正比。

基本过程

最简单的线性查找通过将目标值与各个元素依次比较来寻找目标。从集合起始位置开始、在首次匹配时停止的查找,会返回最早的匹配位置。其他版本则可能返回匹配元素本身、布尔值或所有匹配位置。

下面的伪代码在下标从零开始的数组中执行查找:

linear_search(A, target):
    for i = 0 to length(A) - 1:
        if A[i] == target:
            return i
    return NOT_FOUND

对于数组 [14, 7, 23, 7, 9],查找 7 时会先检查 14,再检查 7,然后返回下标 1。查找 5 时则会检查所有元素,最后返回 NOT_FOUND。空数组不需要进行任何元素比较。

这一方法并不局限于判断相等。线性查找也可以检验某个谓词,例如记录是否具有指定标识符,或测量值是否超过阈值。检验该谓词的开销也计入总运行时间。

正确性

一个有用的循环不变量是:在检查位置 ii 之前,从位置 00 到位置 i−1i-1 的所有元素都不与目标匹配。

初始时,该不变量成立,因为位置 00 之前没有任何元素。如果位置 ii 的元素不匹配,前进到下一个位置后,不变量仍然成立。如果该元素匹配,由于此前的所有位置均已排除,算法返回的就是第一次出现的位置。如果循环结束,则说明所有元素都已检查,且没有找到匹配项。

对于有限集合,每次未找到匹配项的迭代都会使查找位置向前推进,而位置总数有限,因此算法必然终止。

复杂度

时间复杂度取决于首次匹配出现的位置,以及是否存在匹配项。对于基本实现,按元素与目标值之间的比较次数计算,可得:

情况 元素比较次数 运行时间
第一个元素匹配 11 Θ(1)\Theta(1)
首次匹配出现在从 11 开始计数的第 kk 个位置 kk Θ(k)\Theta(k)
只有最后一个元素匹配 nn Θ(n)\Theta(n)
没有元素匹配 nn Θ(n)\Theta(n)

这些运行时间界限假定访问每个后继元素以及进行一次比较都只需常数时间。比较长字符串或结构化对象可能需要额外的工作。

对于非空且恰好包含一个匹配元素的集合,如果该元素出现在每个位置的可能性相同,那么成功查找的比较次数的期望值为

E[C∣success]=1+2+⋯+nn=n+12.\mathbb{E}[C \mid \text{success}] = \frac{1+2+\cdots+n}{n} = \frac{n+1}{2}.

如果查找成功的概率为 pp,并且在成功的条件下,同样满足匹配位置均匀分布的假设,那么

E[C]=pn+12+(1−p)n.\mathbb{E}[C] = p\frac{n+1}{2} + (1-p)n.

因此,要讨论平均情况,就必须明确查询的分布;平均情况并非仅由算法本身决定。

不计集合本身,迭代实现的辅助空间复杂度为 Θ(1)\Theta(1)。存储全部 mm 个匹配项的版本还需要与 mm 成正比的额外空间。

无结构搜索的下界

在没有顺序、索引或其他可用信息时,精确查找可能需要检查每个元素。如果算法尚有元素未检查便报告目标不存在,那么该元素就有可能包含目标。因此,在逐一检查元素且没有额外结构可用的经典模型中,线性查找达到了最优的 Θ(n)\Theta(n) 最坏情况界限。

变体

查找所有匹配项

为了找到每一次出现的位置,算法在找到匹配项后仍会继续执行。它会检查全部 nn 个元素,而不是提前停止。仅统计匹配项数量时可以使用常数辅助空间;收集匹配项则需要空间来存储结果。

哨兵查找

哨兵是放置在已知停止位置上的一个额外目标值。它保证查找循环最终一定会遇到匹配项,从而省去每次迭代中单独判断是否到达集合末尾的检查。

随后,算法会检查找到的匹配项属于原集合,还是仅仅为哨兵。实现时必须提供一个安全的哨兵存放位置。临时替换已有元素的版本必须在查找后恢复该元素,并单独处理空集合。哨兵查找改变的是常数因子,而非线性的最坏情况界限;如果所需的修改不安全或不被允许,就不适合使用这一方法。

查找有序数据

对升序集合进行线性查找时,遇到大于目标值的元素即可停止。不过,有些查找仍需检查整个集合,因此最坏情况下的复杂度仍为线性。

按访问频率排序

对于访问频率已知的重复查找,将经常被查询的元素放在靠前位置,可以减少比较次数的期望值。在每个元素的检查成本相同、不同键组成的集合固定不变的条件下,按查询概率从高到低排列各个键,可以使成功查找的平均比较次数最少。只有在允许改变集合顺序时,才能采用这种重排方式。

数据表示与实际性能

线性查找天然适合链表,因为每个节点都直接指向下一个节点。如果反复按数值下标获取链表元素,可能每次都需要从头遍历链表,使原本线性的扫描变为二次时间。高效的实现只会沿链接遍历一次。

对于连续存储的数组,顺序访问往往能够有效利用 CPU 缓存和硬件预取。因此,尽管线性查找在渐近复杂度上处于劣势,但在小型集合上仍可能具有竞争力。实际性能取决于元素大小、比较成本、内存布局和具体实现。

数据库的表扫描采用类似的方法:逐条检查记录,判断其是否满足条件。在没有可用的数据库索引,或查询需要读取很大一部分记录时,这种扫描可能是合适的选择。

与其他查找方法的比较

二分查找在有序数组上只需对数级的比较次数,但它依赖于数据有序,以及能够高效访问中间位置。仅为回答一次查询而排序,成本可能高于一次线性扫描;如果需要重复查询,这种预处理则可能值得。

在适当的假设下,哈希表可以提供期望为常数时间的查找,但需要额外的存储、构建和维护。二叉搜索树,尤其是平衡二叉搜索树,既支持高效查找,也支持与顺序有关的操作,但同时会引入自身的结构开销。

因此,线性查找适用于小型或未排序的集合、偶尔进行的查询、只能顺序访问的数据,以及现有索引不支持的谓词。它的主要局限在于:查找失败时,或首次匹配出现在接近末尾的位置时,都必须检查几乎整个集合。