查找是一种常用的基本运算。简言之，就是在“大量信息”中查找一个“特定的”信息。这里的大量信息是查找所依赖的数据结构，称之为查找表（Search Table）。查找表是由同一类型的数据元素(或记录)构成的集合。由于集合中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。

与查找有关的基本概念：

（1）关键字

关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。能唯一确定一个数据元素（或记录）的关键字，称为主关键字；而不能唯一确定一个数据元素（或记录）的关键字，称为次关键字。例如，一般情况下“学号”即可看成主关键字，而“姓名”则应视为次关键字，因可能有同名同姓的学生。

（2）查找

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。若查找表中存在这样一个记录，则称“查找成功”，结束查找过程，并给出找到的数据元素（或记录）的信息，或指示该数据元素（或记录）的位置；否则称“查找不成功”，查找结果给出“空记录”或“空指针”。

（3）平均查找长度ASL

为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。

查找可能产生“成功”与“不成功”两种结果，但在实际应用的大多数情况下，查找成功的可能性比不成功的可能性大得多，特别是在表中记录数n很大时，查找不成功的概率可以忽略不计。当查找不成功的情形不能忽视时，查找算法的平均查找长度应是查找成功时的平均查找长度与查找不成功时的平均查找长度之和。

由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。

查找的基本方法可以分为两大类，即比较式查找法和计算式查找法。其中比较式查找法又可以分为基于线性表的查找和基于树的查找，而计算式查找法也称为HASH（哈希）查找法。

（4）数据元素类型

在手工绘制表格时，总是根据有多少数据项，每个数据项应留多大宽度来确定表的结构，即表头的定义。然后，再根据需要的行数，画出表来。在计算机中存储的表与手工绘制的类似，需要定义表的结构，并根据表的大小为表分配存储单元。以图8.1为例，用C语言的结构类型描述之。