在介绍各种查找算法之前，本节先介绍一些基本概念。

（1）查找表是同一类型数据元素（或记录）构成的集合，与4种数据关系中的集合结构对应。由于集合中数据元素之间存在着完全松散的关系，因此，查找表往往要借助其他数据结构来实现相关算法。

（2）关键字是可以标识一个数据元素（或记录）的数据项，关键字的值被称为键值。若关键字可以唯一地标识一条记录，则称此关键字为主关键字（简称主键）；反之，则称此关键字为次关键字。

（3）查找是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素的过程。若在查找表中存在与给定值匹配的记录，则查找成功，此时查找的结果可以是整个记录的信息或查找成功标记等。若在查找表中不存在与给定值匹配的记录，则查找不成功，此时查找结果可以是不成功标记，或将被查找的记录插入查找表。

（4）静态查找表是仅对查找表进行查找操作，而不进行插入和删除操作的查找表。静态查找在查找不成功时，只返回一个不成功标志，不改变查找表，因此表中数据元素的数量不会发生变化。(www.daowen.com)

（5）动态查找表是在查找的同时对表进行插入和删除操作的表。动态查找在查找不成功时，需要将被查找的记录插入查找表，可能会改变查找表，因此表中数据元素的数量可能会发生变化。

（6）平均查找长度（Average Search Length，ASL）是查找过程中关键字的平均比较次数。平均查找长度作为衡量查找算法效率优劣的标准，定义如下：

其中，n是查找表中的元素数量；pi是查找第i个元素的概率，如果每个元素的查找概率相等，则是找到每个元素所需要的比较次数。