有序表的顺序查找

【概述】

顺序查找（Sequential search），又称线性查找，其可分为无序表的查找和有序表的查找

若在查找之前，就已经知道查找表中的关键字是有序的，那么此时的顺序查找即有序表的查找

对于有序表的顺序查找来说，当查找失败时，可以不用再比较到表尾，即可返回查找失败的信息，从而降低查找失败的平均查找长度

【查找过程】

假设表 $L$ 是从小到大排列的，查找的顺序是从前向后，待查找元素的关键字为 key，当查找到第 $i$ 个元素时，发现第 $i$ 个元素对应的关键字小于 key，但第 $i+1$ 个元素对应的关键字大于 key，此时就可以返回查找失败的信息

这是因为第 $i$ 个元素后的所有元素对应的关键字均大于 key，因此查找表中不存在关键字为 key 的元素

可以用如下图所示的查找判定树来描述有序顺序表的查找过程

树中的圆形结点表示有序顺序表中存在的元素，称为成功结点；矩形结点表示有序顺序表中不存在的数据集合，称为失败结点，若有 $n$ 个成功结点，则相应地有 $n+1$ 个失败结点

【平均查找长度】

在有序表的顺序查找中，查找成功的平均查找长度与暴力搜索中的平均查找长度一样，均为：

$$ASL_{成功}=\sum_{i=1}^n \frac{1}{n}\cdot(n-i+1)=\frac{n+1}{2}$$

而当查找失败时，查找指针一定指向了某个失败结点，但失败结点实际上是不存在的，其只是虚构用来表示查找失败的情况

因此，到达失败结点时，所查找的长度，等于其上一层的成功结点所在的层数，故查找不成功时的平均查找长度为：

$$ASL_{失败}=\sum_{j=1}^n q_j(l_j-1)$$

其中，$q_j$ 为到达第 $j$ 个失败结点的概率，在查找概率相等的情况下，有 $q_j=\frac{1}{n+1}$；$l_j$ 为第 $j$ 个失败结点所在的层数

故有：

$$\begin{align} ASL_{失败} &= \sum_{j=1}^n q_j(l_j-1) \notag \\ &= \frac{1}{n+1}\cdot(1+2+...+n+n) \notag \\ &= \frac{n}{2}+\frac{n}{n+1} \notag \end{align}$$