8.1　顺序查找

在介绍顺序查找算法之前,首先介绍几个与查找有关的基本概念。

（1）关键字（key）　数据元素（或记录）中某个数据项的值,用它可以标识数据元素（或记录）。

（2）主关键字（primary key） 可以唯一地标识一个记录的关键字称为主关键字。

（3）次关键字（secondary key） 可以标识若干个记录的关键字称为次关键字。

（4）查找（searching） 在查找表中确定是否存在一个数据元素的关键字等于给定值的操作,称为查找（也称为检索）。若表中存在这样一个数据元素（或记录）,则查找成功；否则查找失败。

（5）内查找和外查找　若整个查找过程全部在内存进行,则称为内查找；若在查找过程中还需要访问外存,则称为外查找。本章中仅介绍内查找。

（6）平均查找长度（ASL）　查找算法的效率,主要是看要查找的值与关键字的比较次数,通常采用平均查找长度来衡量。对一个含有n个数据元素的表,当查找成功时有

其中,p_i为找到表中第i个数据元素的概率,并且有

c_i为查找表中第i个数据元素所用到的比较次数。不同的查找方法有不同的c_i。

查找是许多程序中最消耗时间的一部分。因而,一个好的查找方法会大大提高运行速度。

查找的方法取决于查找表的结构,在表的组织方式中,顺序表是最简单的一种,顺序表是指线性表的顺序存储结构。根据元素之间是否有递增（特性）,查找又分为三种情况:简单顺序查找、二分查找和分块有序查找。顺序查找也称为线性查找,是最简单的一类查找方式,顺序查找既适用于线性表,又适用于链表。

顺序查找对数据的特性没有特殊要求,其基本思想为:从表的一端开始,逐个把每条记录的关键字与给定值k进行比较,若某个记录关键字与给定值k相等,则查找成功,返回找到的记录位置；反之,若已查找到表的另一端,仍未找到关键字值与给定值相等的记录,则查找不成功。

下面以顺序存储为例来介绍,数据元素从下标为1的数组单元开始存放,0号单元留作监测哨,用于存放待查找的值k。

其中,监测哨的作用有以下两方面。

（1）省去判定循环中下标越界的条件,从而可以节约比较时间。

（2）保存查找值的副本,查找时若遇到它,则表示查找不成功。这样在从后向前查找失败时,不必判断查找表是否检测完,从而达到算法统一。

就上述算法而言,对于有n个数据元素的顺序表,给定值k与表中第i个元素关键字相等,即定位第i个记录时,需进行n－i＋1次关键字比较,即c_i＝n－i＋1。在等概率查找的情况下,有

则查找成功时,顺序查找的平均查找长度为

即查找成功时的比较次数约为表长的一半。若k值不在表中,则关键字的比较需要进行n＋1次才能确定查找失败。算法中的基本工作就是关键字的比较,因此,查找长度的量级也即查找算法的时间复杂度,即O（n）。

顺序查找的缺点是当n很大时,平均查找长度较大,效率低；优点是对表中数据元素的存储结构没有要求,无论是用顺序表还是用链表存放记录,也无论记录是否按关键字有序存放均可适用,另外,对于线性链表,只能进行顺序查找。