【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 次

分块检索的优缺点

  • 优点:

  • 插入、删除相对较易

  • 没有大量记录移动

  • 缺点:

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

  • 初始线性表分块排序

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

四、思考

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

参考资料

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

药企,独角兽,苏州。团队长期招人,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn