【数据结构】考研重点掌握：顺序查找算法实现与ASL计算详解

(顺序查找)

线性查找

导读

大家好，很高兴又和大家见面啦！！！

在上一篇内容中，我们系统学习了查找算法的基本概念，包括：

• 查找的定义：在数据集合中寻找满足某种条件的数据元素的过程
• 关键字：数据元素中某个数据项的值，用于标识数据元素
• 平均查找长度（ASL）：衡量查找算法效率的重要指标
• 查找表的分类：静态查找表与动态查找表

这些基础知识为我们深入学习具体查找算法奠定了坚实的理论基础。

今天，我们将正式进入具体查找算法的学习，首先从最基础也是最常用的顺序查找（线性查找）开始。顺序查找作为查找算法家族中最直观、最简单的成员，虽然效率不是最高，但其实现简单、适用性广的特点使其在实际应用中仍然占有重要地位。

在本篇内容中，我们将深入探讨：

• 顺序查找的基本定义和适用场景
• 一般无序线性表的顺序查找实现
• 有序线性表的顺序查找优化
• 哨兵机制在顺序查找中的应用
• 顺序查找算法的时间复杂度分析

通过对比有序表和无序表的查找效率，我们将发现有序性对查找性能的重要影响，这为我们后续学习更高效的查找算法（如二分查找）做好了铺垫。

让我们开始今天的学习之旅吧！

一、顺序查找

1.1 定义

顺序查找也称线性查找，它适用于顺序表和链表。

• 对于顺序表，可以通过数组下标的递增或递减来顺序扫描每个元素
• 对于链表，可以通过指针 next 来依次扫描每个元素

顺序查找通常分为对一般的无序线性表的顺序查找和按关键字有序的线性表的顺序查找。

1.2 一般线性表的顺序查找

1.2.1 算法思想

一般线性表的顺序查找，是一种最直观的查找方法，其基本思想为：

• 从线性表的一端开始，逐个检查关键字是否满足给定的条件
• 若查找到某个元素的关键字满足条件，则查找成功
• 若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则查找失败

1.2.2 算法实现

其具体算法实现如下所示：

typedef int ElemType;
typedef struct SequenceSearchTable {
	ElemType* elem;			// 动态数组
	int Tablelen;			// 表长
}SSTable;					// 顺序查找表
int Search_seq(SSTable ST, ElemType key) {
	for (int i = 0; i < ST.Tablelen; i++) {
		if (ST.elem[i] == key) {
			return i;
		}
	}
	return -1;
}

在该算法下，不管查找表是否有序，都可以实现查找，并且查找的过程既可以从左往右，也可以从右往左。下面我们介绍一下从右往左的顺序查找：

int Search_seq_right_to_left(SSTable ST, ElemType key) {
	ST.elem[0] = key;		// 设置哨兵位
	int i = ST.Tablelen;	// 数组下标
	while(ST.elem[i] != key){
		i -= 1;
	}
	return i;
}

在这次的算法中，我们给查找表中加入了一个哨兵位，且我们将需要查找的关键字的值加入到了哨兵位中，这样就保证了查找表中至少有一个需要查找的值。

在整个查找的过程中，我们只需要通过对比表中的关键字来作为查找的结束条件即可，这样就避免了一些不必要的判断条件，大大提高了程序的效率。

1.2.3 算法效率

接下来我们通过平均查找长度来对该算法进行评价。

假设查找表中存在 n 个元素，那么当我们查找成功时，对于不同查找位置的成功时的关键字比较次数为：

• 位于下标为 n 的元素查找成功：关键字比较 1 次
• 位于下标为 n - 1 的元素查找成功：关键字比较 2 次
• \cdots
• 位于下标为 2 的元素查找成功：关键字比较 n - 1 次
• 位于下标为 1 的元素查找成功：关键字比较 n 次

对于这 n 个元素，每个元素的查找成功概率都相同，即查找概率为：\frac{1}{n} ，那么算法在查找成功时，其平均查找长度为：

$$ \begin{align} ASL_{成功} \notag & = \sum\limits^{n}{i = 1}P_iC_i \ ASL{成功} \notag & = \frac{1}{n} * 1 + \frac{1}{n} * 2 + \cdots + \frac{1}{n} * n \ ASL_{成功} \notag & = \frac{1 + 2 + \cdots + n}{n} \ ASL_{成功} \notag & = \frac{\frac{(n + 1) * n}{2}}{n} \ ASL_{成功} \notag & = \frac{n + 1}{2} \end{align} $$

当查找失败时，我们需要从右往左依次比较关键字，直到比较到哨兵位，因此我们总共需要比较 n + 1 次，即 ASL_{失败} = n + 1。

1.3 有序表的顺序查找

对于一般的线性表，由于其存储的元素不一定有序，因此查找失败时，一定会将表中的所有关键字依次进行比较。

但是如果该线性表有序时，在查找失败的情况下，我们则不需要将表中的所有关键字都进行一次对比。

就比如在线性表 {1, 2, 3, 4, 5, 6, 7, 8, 9} 中，我们要查找的关键字为 10 时，我们在从右往左遍历的过程中，当比较第一个关键字时，我们不难发现，9 < 109 左侧的元素，肯定是比 10 小，因此我们就不需要进行比较。

我们可以通过下面的判定树来描述有序线性表的查找过程，这里我们以有序数组 {10, 20, 30, 40, 50} 为例进行说明：

graph LR
a[10]---> |<|b[20]--->|<|c[30]--->|<|d[40]--->|<|e[50]
a1[(0, 10)]---> |<|a
a2[(10, 20)]---> |<|b
a3[(20, 30)]---> |<|c
a4[(30, 40)]---> |<|d
a5[(40, 50)]---> |<|e
e--->|<|a6[(50, 60)]

在这棵判定树中，矩形结点是有序线性表中的元素，而圆柱形结点是有序线性表中不存在的元素结点，这里我们称之为失败结点。

若有序线性表中有n个元素，那么对应的判定树中就有n个结点，相应地有 n + 1 个失败结点。

在查找的过程中，当查找的值与矩形结点上的值相等时，则查找成功；当需要查找的值位于上图中的圆柱形的关键字范围内时，那就说明查找表中不存在该元素，这就代表我们已经查找失败了，因此就不需要继续往后查找了。

在有序线性表中，查找成功的查找平均长度与无序线性表是一致的，均为 ASL_{成功} = \frac{n + 1}{2}；

当查找失败时，会存在 n + 1 种情况：

• 查找值小于第 1 个元素，关键字比较 1 次
• 查找值大于第 1 个元素，小于第 2 个元素，关键字比较 2 次
• 查找值大于第 2 个元素，小于第 3 个元素，关键字比较 3 次
• \cdots
• 查找值大于第 n - 1 个元素，小于第 n 个元素，关键字比较 n 次
• 查找值大于第 n 个元素，关键字比较 n 次

查找元素的概率均一致，为 P_i = \frac{1}{n + 1} ，那么在有序查找表中，其查找失败的平均查找长度为：

$$ \begin{align*} ASL_{失败} & = \sum\limits^n_{i = 1} P_iC_i \ ASL_{失败} & = \frac{1}{n + 1} * 1 + \frac{1}{n + 1} * 2 + \cdots + \frac{1}{n + 1} * n + \frac{1}{n + 1} * n \ ASL_{失败} & = \frac{1 + 2 + \cdots + n + n}{n + 1} \ ASL_{失败} & = \frac{\frac{n * (n + 1)}{2} + n}{n + 1} \ ASL_{失败} & = \frac{n}{2} + \frac{n}{n + 1} \end{align*} $$

这里我们就以前面展示的判定树的结点数为例来看看有序与无序之间的区别：

• 无序时查找失败的平均查找长度：ASL_{失败} = n + 1 = 5 + 1 = 6
• 有序时查找失败的平均查找长度：ASL_{失败} = \frac{n}{2} + \frac{n}{n + 1} = \frac{5}{2} + \frac{5}{6} = \frac{20}{6} = 3.33

显然，6 > 3.33

不管是有顺序表还是链表，均可以采用顺序查找的方式进行查找操作。而我们后面要介绍的一些查找算法则不适用于链表，如二分查找。

结语

今天的内容到这里就全部结束了，在今天的内容中，我们深入探讨了顺序查找（线性查找）这一基础而重要的查找算法。通过今天的学习，我们掌握了以下核心知识点：

📚 重点内容回顾

1. 顺序查找的基本概念
   • 适用于顺序表和链表的通用查找方法
   • 分为无序线性表和有序线性表两种场景
2. 算法实现技巧
   • 普通顺序查找的实现原理：从查找表的一侧开始，依次检查表中的各个元素，直到找到查找成功或者查找失败
   • 哨兵机制的优化应用，通过减少判断条件提升效率
   • 从右向左查找的实现方式
3. 算法效率分析
   • 查找成功时的平均查找长度：ASL_{成功} = \frac{n + 1}{2}
   • 无序表查找失败：ASL_{失败} = n + 1
   • 有序表查找失败：ASL_{失败} = \frac{n}{2} + \frac{n}{n + 1}
4. 有序表的优势
   • 通过判定树模型直观理解查找过程
   • 有序性在查找失败时能提前终止，显著提升效率

🚀 下期预告

在下一篇内容中，我们将深入探讨二分查找算法，这是一种基于有序表的高效查找方法，时间复杂度可达O(\log n)。我们将从算法原理、实现细节到实际应用进行全面解析，帮助大家掌握这一重要的查找技术。

如果今天的内容对你有帮助，请不要忘记

感谢各位朋友的耐心阅读和支持！学习数据结构与算法是一个循序渐进的过程，坚持就是胜利。咱们下一篇再见，一起探索更高效的查找算法！