顺序查找

1. 考点：基础概况

1.1 知识点概览

查找算法 —— 顺序查找（Linear Search / Sequential Search）

• 基本思想​：
  将待查找的关键字为 ​key​ 的元素从头到尾与表中元素进行比较，如果中间存在关键字为 ​key 的元素，则返回查找成功；否则，返回查找失败。

• 查找成功时的平均查找长度（ASL，Average Search Length，等概率情况下） ：

  $$\text{ASL} = \sum_{i=1}^{n} P_i \cdot (n-i+1) = \frac{1 + 2 + \cdots + n}{n} = \frac{n+1}{2}$$

1.2 解析说明

• 核心原理：
  顺序查找对表中的数据结构没有要求（既适用于线性表中的顺序存储，也适用于链式存储）。

• ASL 计算推导（以从头到尾查找为例） ：

  • 查找第 $1$ 个元素（排在表头）：需要比较 $1$ 次（若按从前往后数，找到第一个元素比较 1 次，第二个比较 2 次……此处公式中对应从尾部或其他方向数，但在等概率情况下总和相同）。

  • 查找第 $i$ 个元素：需要比较 $i$ 次。

  • 所有元素查找次数的总和为 $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$。

  • 在等概率情况下（每个元素被查找的概率 $P_i = \frac{1}{n}$），平均查找长度为：

    $$\text{ASL}_{\text{成功}} = \frac{1 + 2 + \cdots + n}{n} = \frac{\frac{n(n+1)}{2}}{n} = \frac{n+1}{2}$$

1.3 核心结论

• 顺序查找在查找成功时的平均查找长度为 ​**$\frac{n+1}{2}$**。
• 时间复杂度为 ​**$O(n)$**。