9.7.1　基本概念

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算。

查找定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）

查找算法可以分为无序查找和有序查找。

·无序查找：被查找数列有序无序均可；

·有序查找：被查找数列必须为有序数列。

平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=Pi*Ci的和。

Pi：查找表中第i个数据元素的概率。

Ci：找到第i个数据元素时已经比较过的次数。