查找表（Search Table）是由一些具有相同可辨认特性的数据元素（或记录）构成的集合。
对查找表经常进行的操作有：
（1）查询某个"特定的"数据元素是否在表中；
（2）检索某个"特定的"数据元素的各种属性；
（3）在查找表中插入一个数据元素；
（4）从查找表中删除某个数据元素。
在实际应用中的查找表通常可分两类：其中一类查找表在使用时主要作前两种统称为"查找"的操作，称此类查找表为静态查找表（Static Search Table）。
若在对查找表进行查找的过程中，同时需要随时插入当前查找表中不存在的数据元素，或者从当前的查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表（Dynamic Search Table）。
由于"集合"中的数据元素之间的关系未作限定，因此在集合中查询或检索一个"特定的"数据元素时，无规律可遵循，只能对集合中的元素一一加以辨认直至找到为止。而这样的"查询"或"检索"是任何计算机应用系统中使用频度都很高的操作，因此设法提高查找表的查找效率，是本章讨论问题的出发点。
在日常生活中，人们几乎每天都要进行"查找"工作。例如，在电话号码簿中查阅"某单位"或"某人"的电话号码，在字典中查阅某个"字"的读音和意义等等。"电话号码簿"和"字典"都可看作是静态查找表，而旅馆中留宿旅客的名单则是一个动态查找表。在各种系统软件或应用软件中，查找表是最常用的数据结构之一，如编译程序的符号表，信息处理系统的信息表等等。
查找（searching）根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。若表中存在这样的一个元素，则称查找是成功的，此时查找的结果为给出整个数据元素的信息，或指示该数据元素在查找表中的位置；若表中不存在这样的元素，则称查找不成功，此时查找的结果可给出一个"null"元素（或空指针）。
如何评价查找算法的时间效率？由于查找算法中为确定其关键字等于给定值的数据元素的基本操作为"关键字和给定值相比"，因此通常以查找过程中关键字和给定值比较的平均次数作为比较查找算法的度量依据。
定义：查找过程中先后和给定值进行比较的关键字个数的期望值称作查找算法的平均查找长度(Average Search Length)。
对于含有 n 个记录的查找表，查找成功时的平均查找长度为
其中：
为查找表中第 i 个记录的概率，且
为找到表中第 i 个记录（其关键字等于给定值）时，曾和给定值进行过比较的关键字的个数，显然，
的值将随查找过程的不同而不同。
可以想像得到，如果能有目标地进行查找肯定是比在一大堆事物中瞎摸要有效得多，因此为提高查找效率，一个办法就是在构造查找表时，在集合中的数据元素之间人为地加上某种确定的约束关系。本章正是讨论查找表的各种组织方法及其查找过程的实施。
在本章以后各节讨论中涉及的数据元素(记录)将统一定义为如下描述的类型：
typedef struct
{
KeyType key; //
关键字项
…… // 其它数据项
} ElemType; //
数据元素类型
其中的关键字类型可以为整型、实型、字符型、串类型等。