07-7.1.1 查找的基本概念

👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

基本概念

查找 —— 在数据集合中寻找满足某种条件的数据元素的过程
查找表（查找结构） —— 用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成
关键字 —— 数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的

Eg:
查找表：微信用户数据集（图结构）
数据元素（记录）：每个用户的信息
关键字：微信号（唯一）

对查找表的常见操作

1. 查找符合条件的数据元素
2. 插入、删除某个元素
   只需进行操作① —— 静态查找表，仅关注查找速度即可
   也要进行操作② —— 动态查找表，除了查找速度，也要关注插入、删除操作是否方便实现

查找算法的评价指标

查找长度 —— 在查找运算中，需要对比关键字的次数
平均查找长度（ASL，Average Search Length）—— 所有查找过程中进行关键字的比较次数的平均值
$$ASL=\sum _{i=1}^n{P}_i{C}_i$$

$n$ ：数据元素个数
$P_i$ ：查找第 i 个元素的概率
$C_i$ ：查找第 i 个元素的查找长度