查找概述

在计算机科学中，查找的定义是在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素。即根据某个给定的值，在数据元素的集合中找到某个特定的值。这个由数据元素构成的集合称为查找表。

一个数据元素由若干个数据项组成，如果数据元素中某个数据项的值能够唯一标识一个数据元素，则称之为关键字。给定一个关键字，根据这个关键字来查找表中相应的元素，若找到，则查找成功；若未找到，则查找失败。

在计算机中进行查找运算时，首先要确定数据的组织形式，即用的是哪种数据结构存储数据。不同数据结构以及数据在存储空间的排列方式对查找的效率可能有很大的影响。因此在选择排序算法时，要先了解算法所对应数据的组织形式以及数据的排列方式。在查找过程中，进行查找的数据结构称为查找表，对查找表所进行的操作主要有：查找某个元素是否存在；查找某个元素的各种属性；在查找表中插入一个元素；删除查找表中的某一个元素。

如果在查找的同时只对查找表进行前两种操作，即只是查找出某一个数据并不对查找表进行修改，则称此类查找表为静态查找表。例如只在表中查找某个学生的学籍信息、或者只在表中查询某次航班的信息等，这样的表就是静态查找表。

如果在查找过程中还会对查找表进行其它操作，如插入不存在的数据元素，或者从查找表中删除已经存在的某个数据元素等，则称这样的查找表为动态查找表。动态查找表与静态查找表的使用都很广泛。

在查找时，通常把对关键字的最多比较次数和平均比较次数作为查找算法性能分析时的两个基本依据，前者叫作最大查找长度(Maximum Search Length ， MSL)， 后者叫做平均查找长度 (Average Search Length ， ASL)。查找运算的主要操作就是关键字的比较，所以把查找过程上对关键字需要执行的平均比较次数（平均查找长度）作为衡量查找算法性能优劣的标准。平均查找长度 ASL(Average Search Length)定义为：

其中n是元素的个数，Pi 是查找第i个元素的概率，如果没有特别声明，认为每个元素的查找概率是相等的，即P1=P2=P3…=Pn =1/n；Ci是找到第i个元素时，与给定值已经进行过的比较次数。