【10.2】检索--线性表的检索

一、顺序检索

• 针对线性表里的所有记录，逐个进行关键 码和给定值的比较

• 若某个记录的关键码和给定值比较相等，则 检索成功

• 否则检索失败(找遍了仍找不到)

• 存储:可以顺序、链接

• 排序要求:无

“监视哨”顺序检索算法

顺序检索性能分析

检索成功:假设检索每个关键码等概率 Pi = 1/n

检索失败:假设检索失败时都需要比较 n+1 次 (设置了一个监视哨)

顺序检索平均检索长度

假设检索成功的概率为 p，检索失败的概率为 q=(1-p)

顺序检索优缺点

• 优点:插入元素可以直接加在表尾 Θ(1)
• 缺点:检索时间太长 Θ(n)

二、 二分检索

• 将任一元素 dataList[i] .Key 与给定值 K 比较， 三种情况:

• (1)Key = K，检索成功，返回 dataList[i]

• (2)Key > K，若有则一定排在 dataList[i]前

• (3)Key < K，若右则一定排在 dataList[i]后

• 缩小进一步检索的区间

二分法检索算法

二分法检索性能分析

三、 分块检索

• “按块有序”

• 设线性表中共有 n 个数据元素，将表分成 b 块

• 前一块最大关键码必须小于后一块最小关键码

• 每一块中的关键码不一定有序

• 顺序与二分法的折衷

• 既有较快的检索

• 又有较灵活的更改

分块检索——索引顺序结构

分块检索性能分析

分块检索为两级检索:

• 先在索引表中确定待查元素所在的块，ASLb * 然后在块内检索待查的元素，ASLw

• 假设在索引表中用顺序检索，在块内也用顺序检索

当 n=10,000 时：

• 顺序检索 5,000 次
• 二分法检索 14 次
• 分块检索 100 次

分块检索的优缺点

• 优点:

• 插入、删除相对较易

• 没有大量记录移动

• 缺点:

• 增加一个辅助数组的存储空间

• 初始线性表分块排序

• 当大量插入/删除时，或结点分布不均匀时， 速度下降

四、思考

• 试比较顺序检索、二分检索和分块检索的 优缺点。 这几种检索方法适合的应用场景分别是什 么?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾