2022.09.15
查找。在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：一是查找成功，即在数据集合中找到了满足条件的数据元素：二是查找失败。
查找表（查找结构）。用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成，可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有4 种： ① 查询某个特定的数据元素是否在查找表中； ② 检索满足条件的某个特定的数据元素的各种属性； ③ 在查找表中插入一个数据元素； ④ 从查找表中删除某个数据元素；
静态查找表。若一个查找表的操作只涉及上述操作①和②，则无须动态地修改查找表，此类查找表称为静态查找表。与此对应，需要动态地插入或删除的查找表称为动态查找表。
适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；
适合动态查找表的查找方法有二叉排序树的查找、散列查找等。二叉平衡树和 B树都是二叉排序树的改进。
关键字。数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中 “学号”这一数据项的值唯一地标识一名学生。
平均查找长度。在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为
式中，n是查找表的长度：P,是查找第i个数据元素的概率，一般认为每个数据元素的查找概率相等，即Pi=1/n：C;是找到第i个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。