学习笔记--数据结构与算法基础（青岛大学-王卓）--第七章查找算法-阿里云开发者社区

学习笔记--数据结构与算法基础（青岛大学-王卓）--第七章查找算法

2022-05-25 574

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 学习笔记--数据结构与算法基础（青岛大学-王卓）--第七章查找算法

视频链接
在这里插入图片描述
数据结构与算法基础（青岛大学-王卓）--第七章查找

本章知识框架
在这里插入图片描述

1.查找的基本概念

什么是查找表?

在这里插入图片描述

什么是关键字

在这里插入图片描述

什么是查找

在这里插入图片描述

查找是否成功?

查找的目的?

在这里插入图片描述

查找的分类

在这里插入图片描述

如何评价查找算法

在这里插入图片描述

查找过程中我们需要研究什么?

在这里插入图片描述

2.线性表的查找

对于这一部分,该视频讲解了顺序查找(线性查找),折半查找(二分或对分查找)和分块查找这三类查找。
在这里插入图片描述

顺序查找(线性查找)
在这里插入图片描述

顺序查找

在这里插入图片描述
算法1:
算法2:

算法3:

算法改进:

把待查关键字key存入表头（“哨兵”、”监视哨”)，从后往前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。

在这里插入图片描述

对改进算法的时间效率进行分析:

顺序查找的特点:
在这里插入图片描述

折半查找(二分或对分查找【查找表必须是有序表】)
什么是折半查找:
在这里插入图片描述
非递归算法:

递归算法:

int Search Bin(SSTable ST, KeyType key,int low ,int high){
    if(low > high) return 0;
    mid = (low + high)/2;
    if(key == ST.elem[mid].key) return mid;
    else if(key < ST.elem[mid].key)
        high = mid - 1;
    else
        low = mid + 1;
    Bin(ST,key,low,high);
}

折半查找的性能分析
在这里插入图片描述

分块查找(索引顺序查找)
分块查找:
下面查38,先选择块(38大于22并且小于48所以在索引表序号7开始的块中即第二块),再从块内进行查找(通过顺序查找,即可找到38位于序号10)
在这里插入图片描述
分块查找性能分析:

分块查找优缺点:

顺序,折半和分块查找的方法比较

![在这里插入图片描述](https://ucc.alicdn.com/images/user-upload-01/d25381a023c54f04b2ed7f2102ccd384.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Zif5Zif55qE56iL5bqP5ZGY6ZOy5bGO5a6Y,size_15,color_FFFFFF,t_70,g_se,x_16)