2.顺序查找和折半查找

顺序查找

【课件】7.2.1顺序查找

一般线性表

从线性表的一端开始,逐个检查关键宇是否满足给定的条件。
引入“哨兵”^[1]可以避免很多不必要的判断语句,从而提高程序效率。

对于有 $n$ 个元素的表, 给定值 key 与表中第 $i$ 个元素相等, 即定位第 $i$ 个元素时, 需进行 $n-i+1$ 次关键字的比较, 即 $C_{i}=n-i+1$ 。查找成功时, 顺序查找的平均长度为

\mathrm{ASL}_{\text {成功 }}=\sum_{i=1}^{n} P_{i}(n-i+1)

当每个元素的查找概率相等, 即 $P_{i}=1 / n$ 时, 有

\mathrm{ASL}_{\text {成功 }}=\sum_{i=1}^{n} P_{i}(n-i+1)=\frac{n+1}{2}

查找不成功时, 与表中各关键字的比较次数显然是 $n+1$ 次, 即 $\mathrm{ASL}_{\text{不成功}}$ $=n+1$ 。

有序表的顺序查找

当查找到第 $i$ 个元素时, 发现第 $i$ 个元素对应的关键字小于 key, 但第 $i+1$ 个元素对应的关键字大于 key, 这时就可返回查找失败的信息, 因为第 $i$ 个元素之后的元素的关键字均大于 key, 所以表中不存在关键字为 key 的元素。

可以用如图所示的判定树来描述有序线性表的查找过程。树中的圆形结点表示有序线性表中存在的元素；树中的矩形结点称为失败结点（若有 $n$ 个结点，则相应地有 $n+ 1$ 个查找失败结点)，它描述的是那些不在表中的数据值的集合。若查找到失败结点，则说明查找不成功。

\mathrm{ASL}_{\text{不成功 }}=\sum_{j=1}^{n} q_j \left(l_j-1\right)=\frac{1+2+\cdots+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}

式中, $q_{j}$ 是到达第 $j$ 个失败结点的概率, 在相等查找概率的情形下, 它为 $1 /(n+1) ; l_{j}$ 是第 $j$ 个失败结点所在的层数。当 $n=6$ 时, $\mathrm{ASL}_{\text {不成功 }}=6 / 2+6 / 7=3.86$ , 比一般的顺序查找算法好一些。

折半查找

折半查找又称二分查找,它仅适用于有序的顺序表。

折半查找的过程可用图所示的二叉树来描述,称为判定树

例如, 已知 11 个元素的有序表 $\{7,10,13,16,19,29,32,33,37,41,43\}$ , 要查找值为 11 和 32 的元素, 指针 low 和 high 分别指向表的下界和上界, mid 则指向表的中间位置 $\left\lfloor (\text{low}+\text{high}) /2\right\rfloor$ ^[2] 。以下说明查找 11 的过程

数值	7	10	13	16	19	29	32	33	37	41	43
序号	1	2	3	4	5	6	7	8	9	10	11

提示

对应判定树的中序序列是一个有序序列，例如:

可以对比下面这道真题理解

若有序序列有 $n$ 个元素,则对应的判定树有 $n$ 个圆形的非叶结点和 $n+1$ 个方形的叶结点。显然,判定树是一棵平衡二叉树。且如果mid 则指向表的中间位置 $\left\lfloor (\text{low}+\text{high}) /2\right\rfloor$ 向下取整，则对任意一个结点，右子树个数-左子树=0或1

由上述分析可知, 用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率查找时, 查找成功^[3]的平均查找长度为

\mathrm{ASL}=\frac{1}{n} \sum_{i=1}^{n} l_{i}=\frac{1}{n}\left(1 \times 1+2 \times 2+\cdots+h \times 2^{h-1}\right)=\frac{n+1}{n} \log _{2}(n+1)-1 \approx \log _{2}(n+1)-1

式中, $h$ 是树的高度, 并且元素个数为 $n$ 时树高 $h=\left\lceil\log _{2}(n+1)\right\rceil$ 。所以, 折半查找的时间复杂度为 $O\left(\log _{2} n\right)$ , 平均情况下比顺序查找的效率高。

在图 7.2 所示的判定树中, 在等概率情况下, 查找成功 (圆形结点) :

\mathrm{ASL}=(1 \times 1+2 \times 2+3 \times 4+4 \times 4) / 11=3

查找不成功 (方形结点) :

\mathrm{ASL}=(3 \times 4+4 \times 8) / 12=11 / 3

提示

以上的结论是针对于

\text{mid}=\left\lfloor (\text{low}+\text{high}) /2\right\rfloor

若为向上取整，则结论反过来

时间复杂度 $O(\log_{2}n)$

分块查找

分块查找又称索引顺序查找,它吸取了顺序查找和折半查找各自的优点,既有动态结构,又适于快速查找。

基本思想

将查找表分为若干子块。块内的元素可以无序,但块间的元素是有序的,即第一个块中的最大关键字小于第二个块中的所有记录的关键字,第二个块中的最大关键宇小于第三个块中的所有记录的关键字,以此类推。再建立一个索引表,索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址,素引表按关键字有序排列。

例如，关键码集合为 $\{88,24,72, 61,21,6,32,11,8,31,22,83,78,54\}$ ，按照关键码值 $24,54,78,88$ ，分为4个块和索引表，如图所示。

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均查找长度分别为 $L_{\mathrm{I}}, L_{\mathrm{S}}$ , 则分块查找的平均查找长度为

\mathrm{ASL}=L_{\mathrm{I}}+L_{\mathrm{S}}

将长度为 $n$ 的查找表均匀地分为 $b$ 块, 每块有 $s$ 个记录, 在等概率情况下, 若在块内和索引表中均采用顺序查找, 则平均查找长度为

\mathrm{ASL}=L_{\mathrm{I}}+L_{\mathrm{S}}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^{2}+2 s+n}{2 s}

此时, 若 $s=\sqrt{n}$ , 则平均查找长度取最小值 $\sqrt{n}+1$ 。

拓展

若查找表是动态查找表，需要增删改，则该用链式存储更方便

总结

ST.elem [0]=key;，查找时从后往前 ↩︎
向下取整 ↩︎
查找不成功的则要根据判定树具体计算 ↩︎

2.顺序查找和折半查找

# 顺序查找

# 一般线性表

# 有序表的顺序查找

# 折半查找

# 分块查找

# 总结

顺序查找

一般线性表

有序表的顺序查找

折半查找

分块查找

总结