数据结构——查找（一、什么是查找？）

一、查找的基本概念

1、在数据集合中寻找满足某种条件的数据元素的过程称为查找。

查找的结果分为 查找成功 和 查找失败

2、查找表——用于查找的数据集合

注：查找表并不是新的数据结构，查找在线性表、链表等结构中进行。

对查找表的常见操作：

查询符合条件的数据元素

插入、删除数据元素

3、静态查找表——对查找表只涉及查找操作

适合静态查找表的查找方法：顺序查找 、折半查找、散列查找等。

4、动态查找表——需要动态插入或删除的查找表

适合动态查找表的查找方法：二叉排序树的查找、散列查找。

注：对于动态查找，除了关注查找速度，还需要关注删插速度。

5、关键字——数据元素中唯一标识的某个数据项的值

使用基于关键字的查找，查找结果应该是唯一的。

例如，学生的学号是关键字，由于同名同姓的存在，学生的姓名不是关键字。

6、一次查找的长度——在查找过程中，需要比较关键字的次数

平均查找长度（ASL）——每次查找关键字的比较次数的平均值

n是查找表的长度，是查找第i个数据元素的概率，一般情况，;

是找到第i个数据元素所需要进行的比较次数。

注：通常会对查找成功和查找失败两种方式进行统计。

平均查询长度的计算方法请参考顺序查找的平均查找长度、折半查找的平均查找长度等~

数据结构——查找（2、顺序查找、折半查找和分块查找）-CSDN博客