查找的基本概念¶

查找¶

在数据结构中寻找满足某种条件的数据元素的过程称为查找。

查找的结果一般只有成功与失败两种情况。

查找表¶

用于查找的数据集合称为查找表，由同一类型的数据类型（或记录）组成。

对查找表的常见操作有:

• 查询符合条件的数据元素

• 插入、删除数据元素

静态查找表与动态查找表¶

若一个查找表的操作只涉及查找操作，则无需动态地修改查找表，此类查找表称为静态查找表；与之对应的，需要动态地插入或删除的查找表称为动态查找表。

• 适用于静态查找表的查找方法有顺序查找、折半查找、分块查找、散列查找等

• 适用于动态查找表的查找方法有二叉排序树、散列查找等

关键字¶

数据元素中唯一标识该元素的某个数据项的值称为关键字。使用基于关键字的查找，查找的结果应该是唯一的。

平均查找长度¶

在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字比较次数的平均值，其数学定义为:

其中，\(p_i\) 是查找第 \(i\) 个数据元素的概率（一般认为每个数据元素的查找概率相等，即 \(p_i = \frac{1}{n}\)）；\(c_i\) 是查找第 \(i\) 个数据元素时需要比较的关键字次数。

平均查找长度是衡量查找算法效率的重要指标，越小表示算法效率越高。