查找的定义：给定一个值k，在含有n个记录的表中找出关键字等于k的记录。若找到，则查找成功，返回该记录的信息或者该记录在表中的位置；否则查找失败，返回相关的指示信息。

上面是查找的标准定义，其中有两个重要的信息：记录和关键字。在考研中，对于本章算法部分，记录即为关键字，二者不需要过分地去区分。例如，某些数据结构辅导书中定义了一个记录的结构类型如下：

上述语句定义了一个记录，里面包含的内容除了关键字外，还有很多其他内容。而进行查找时是靠关键字域来区分不同的记录的，和记录中的其他内容无关。因此可以把记录简化，让记录中只存在关键字，关键字本身就是记录的全部，上述结构体就可以简化成一句intkey；。考研中对查找题目的考查绝大多数都是这样的，查找表中的记录就是关键字本身，而完全没有必要把记录做成一个结构体，凸显出关键字和记录中其他域的区别。记录组织成一个查找表，在进行查找时，可以把表中的记录、记录的关键字理解成同一个概念（虽然这样理解不太严格）。

采用何种方法进行查找的相关因素如下：

1）使用哪种数据结构来表示查找表，即查找表中的记录是按照何种方式组织的。

2）查找表中关键字的次序，即对无序集合查找还是对有序集合查找。(www.daowen.com)

例如，查找表是用顺序表来表示还是用链表来表示，查找表中的关键字是有序的还是无序的，这都关系到查找方法的选取。

由于查找算法的基本操作是关键字的比较，并且关键字比较次数与待查找关键字有关（对于一个查找表来说，对其中不同的关键字进行查找，关键字比较次数一般不同），因此通常把查找过程中对关键字的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度用ASL来表示，其定义为

式中，n是查找表中记录的个数；p_i是查找第i个记录的概率，在考研题目中p_i一般取1/n；c_i是找到第i个记录所需要进行比较的次数，即查找长度。

这里的平均查找长度其实就相当于之前算法时间复杂度分析中讲到的f（n）。f（n）反映了算法对于规模为n的数据所要执行的基本操作次数。ASL表达式中的c_i是在规模为n的查找表中找到第i个记录所需要进行的比较次数，即基本操作的执行次数。c_i可以写为g（n，i）。由此可见，查找算法中基本操作的执行次数不是由n一个变量来决定的，而是由n和i共同决定的。i的取值不唯一，为了能近似地反映其基本操作的执行次数，必须根据i所有可能的取值来求一个平均值。查找算法的基本操作的执行次数可以表示为。由此可见，f（n）和ASL的地位是一样的，知道了ASL就可以求出一个查找算法的时间复杂度。本节对于查找算法的性能分析重在分析ASL。