5 查找

第5讲 查找

本章主要掌握如下内容：

查找的基本概念，顺序查找法，折半查找法，B-树、散列表及其查找，查找算法的分析与应用。

知识点分析

(一) 查找的基本概念

1．查找的定义

在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是“关键字值等于某个给定值”，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。

2．各种术语

1）查找表：用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。

2）静态查找表：若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。

3）动态查找表：若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。

4）关键字：是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。

5）查找表的存储结构：查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。

6）查找算法的时间效率：查找过程的主要操作是关键字的比较，所以通常以“平均比较次数”来衡量查找算法的时间效率。

(二) 顺序查找法

1．基本思想

顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。顺序表的数据结构及查找算法如下：

typedef struct {

KeyType key ; //关键字域，KeyType可以看成是int , float，char等

„

｝ElemType;

typedef struct {

ElemType * elem ; //数据元素存储空间初始地址，0号单元留空

int length ;

} SSTable ;

int Search_Seq( SSTable ST , KeyType key) {

//在顺序表ST中顺序查找关键字等于key的数据元素。若找到，函数返回该元素位置，否则返回0

ST.elem[0].key = key ; //设置监视哨

for ( i = ST.length ; (ST.elem[i].key != key) ; --i) ;

//从顺序表的最后面向前找，如果不相等，则一直向前找。如果从最后面的元素（ST.elem[ST.length]）到第一个元素（ST.elem[1]）的关键字key都不等于key，则一定会比较到监视哨处（ST.elem[0]）。可以看出，因为我们已经人为设定了ST.elem[0].key

= key，则for循环肯定最迟能到此结束。

return i ; //如果返回0，则说明没有找到（把人为设置的监视哨找到了），否则返回i（i>0）。

｝

2．算法分析

利用比较次数的平均值作为衡量标准（平均查找长度：ASL）

ASL（Average Search Length）定义：

ASL ＝ niPiCi1 (设查找表有n个记录，记录从1开始编号)

其中Pi是查找第i个元素的概率，有niPi1=1。如果查找是等概率的，则有Pi＝1/n（i＝1,2,...n），

Ci是查找第i个元素时和关键字比较的次数，假设从后往前找，则Ci ＝ n－i＋1，从前往后找，则有Ci＝i（i＝1,2,...n）有：

ASL ＝niPiCi1 ＝ 1/n niin1)1( ＝ 1/n（n + (n-1) + (n-2) +...+1） = (n+1)/2

即：在等概率情况下，顺序查找法的平均查找长度为（n+1）/2。

说明：顺序查找算法简单，对表的结构无任何要求；但是执行效率较低，尤其当n较大时，不宜采用这种查找方法。

『经典例题解析』

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n

【答案】 C。

2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )

A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2

【答案】 A。

(三) 折半查找法

1．基本思想

折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或降序）排列，也就是说折半查找只适用于对有序顺序表进行查找。有序顺序表也称为有序表。

折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值k与中间位置结点的关键字比较，若相等，则查找成功;否则，根据比较结果缩小查找范围，如果k的值小于关键字的值，根据

查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若k的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小为空即查找失败为止。

举例：有一个有序的线性表，其元素个数为11，排列如下。请给出在该表中查找21的过程。

5 12 19 21 37 56 64 75 80 88 92

查找过程如下：设以上元素保存在一维数组R中，从R[1]开始保存。

元素下标 1 2 3 4 5 6 7 8 9 10 11

元素关键字 5 12 19 21 37 56 64 75 80 88 92

第一步：

设low指向首元素（赋值为1），high指向尾元素（赋值为11），计算下边中值得：

mid ＝ (low +high)/2 = 6

则有 R[mid]=R[6]=56 > 21

第二步：由以上判断可知，如果记录中存在21，则一定在R[6]之前（因为R是非递减有序的）。故修改low和high如下：

low值不变，仍然有low＝1；

high的值修改：使其指向R[6]的前一个元素，即使high＝mid－1 ＝ 6－1=5 ;

比较范围缩小至R[1]～R[5]。原因：如果R[6]比21大，则R[6]后面的所有元素都比21大，所以就没有必要再到R[6]后面查找21了。

mid ＝ (low +high)/2 = 3

则有R[mid]＝R[3]＝19<21

第三步：由以上判断可知，如果记录中存在21，则一定在R[3]之后（同样因为R是非递减有序的）。故修改low和high的值如下：

low的值修改，使其指向R[3]的下一个元素，即low＝mid＋1＝3+1＝4;

high不变，仍然是5。

mid ＝ (low +high)/2 =4

则有R[mid]＝R[4]＝21 查找成功。

2．算法分析

具体算法为：

int Search_Bin(SSTable ST , KeyType key)

{ //从ST表中查找key，若找到则返回下标，否则返回0 low=1 high=11 mid

low=1 high=5 mid 元素下标 1 2 3 4 5 6 7 8 9 10 11

元素关键字 5 12 19 21 37 56 64 75 80 88 92

high=5 mid 元素下标 1 2 3 4 5 6 7 8 9 10 11

元素关键字 5 12 19 21 37 56 64 75 80 88 92

low=4

low = 1 ; high = ST.length ;

while (low <= high) {

mid = (low + high) / 2 ;