8.2 有序表的查找在线视频

同学们大家好

我是云南大学信息学院教师孔兵

这节课我们讨论有序表的查找

如果查找表中的记录在数组中是按照关键字有序存储的话

称之为有序表

对有序表可以采用更高效的查找算法---折半查找

折半查找是先确定待查记录所在的范围或者叫区间

然后逐步缩小范围直到找到或找不到和给定值相等的记录为止

假设要查找的给定值是key

初始化的查找区间是整个查找表

用low表示查找区间的低端

初始low=1，用high表示查找区间的高端

初始high=ST.length，这是表中最后一个元素的位置

随后，mid=(low+high)/2计算区间中点的位置

用给定值key和mid位置记录的关键字比较

有三种情况，一是二者相等，意味着查找已经成功

返回记录的位置mid

二是给定值小于mid的关键字

那么根据有序表的特征，应该在前半区间中继续查找

置区间的高端high=mid-1，缩小查找范围

三是给定值大于mid的关键字

应该在后半区间中继续查找

置区间低端low=mid+1，同样缩小查找范围

重复上述过程

直到找到或找不到和给定值相等的记录为止

下面结合图例具体看一下折半查找的过程

设要查找的给定值是21，查找表情况如图

图中只给出了记录的关键字

初始low=1，high=11。开始折半查找

计算mid结果是6

给定值21小于mid的关键字56

high=mid-1=5，缩小查找范围

继续折半查找，mid=3,给定值21大于mid的19

low=mid+1=4

继续，mid=4，4号位置的关键字和给定值相等

查找成功，返回记录位置4

整个查找给定值21的过程中

给定值和关键字比较了3次

这是查找成功的一个实例

下面看一下查找失败的一个例子

假设要查找的给定值是28

前面几步查找的过程和查找21是一样的

当28和4号单元的21比较，并比21大

low=4+1=5,这个时候

实际要查找范围只有一个元素

Low和high都等于5，计算mid也等于5

那么28小于5号单元的37，high=mid-1=4

这时，查找的低端low大于查找的高端high

查找的范围已经不存在了

意味着查找失败，return 0

整个查找给定值28失败的过程中

给定值和关键字比较了4次

这是查找失败的一个例子

下面看一下，折半查找函数的实现

函数的返回值和参数的含义和顺序查找相同

这就不重复了

进入函数以后，首先设置查找范围

low=1; high=ST.length

随后，当low小于等于high的时候

循环进行折半查找，也就是查找区间存在的情况下

继续循环进行查找

计算区间的中点mid，进入嵌套的if语句

如果给定值key等于mid位置的关键字

那么查找成功，返回记录的位置mid

退出查找函数

否则，如果给定值小于mid的关键字

high=mid-1，缩小查找区间到前半区间

再否则，给定值不等于，也不小于mid的关键字

那么肯定是大于

low=mid+1，缩小查找区间到后半区间

继续下一次循环进行折半查找

如果循环条件不成立，low大于high

这意味着查找失败

那么循环结束，返回0

那么折半查找的性能如何呢？

我们对折半查找进行查找性能分析

为了方便分析

我们把折半查找的过程用一棵二叉树来加以描述

这样的二叉树称为判定树

观察图，结合刚才的实例看一下

判定树的根是6，其含义是折半查找的时候

第6个位置是初始化区间中点mid的位置

也是第一个被比较的记录的位置

根据折半查找过程

如果给定值和mid的关键字相等，则查找成功返回

也就是说，如果查找的给定值是56的话

只需要和关键字比较一次，就可以查找成功

如果给定值小于56

那么我们就到前半区间1~5中查找

结点6的左子树描述了在前半区间的查找

左子树的根3说明区间1~5中第1个被比较记录的位置

如果查找的给定值是19，要和关键字比较2次

可以查找成功

如果给定值小于19

继续查找区间1~2，子树的根是1

如果查找的给定值是05

要和关键字比较3次，可以查找成功

小于05，查找失败，大于05，到右子树查找

查找区间为2~2，区间只有1个记录

如果查找的给定值是13，要和关键字比较4次

可以查找成功

小于或大于13都是失败

树中其它分支的情况雷同

通过这样一棵判定树

把对实例的查找过程做了一个静态的描述

总结一下，记录查找成功的比较次数

就是到从根到判定树中该记录对应结点路径上结点的数目

或者是该结点的层次数

例如记录21对应的结点4在判定树的第三层

那么记录21查找成功需要3次和关键字的比较

从判定树可以直观的看到

11个记录，1次比较成功的有1个记录56

2次比较成功的有2个记录19和80

3次比较成功的有4个记录

4次比较成功的有4个记录

考虑是等概率的情况下

我们可以计算查找成功的平均查找长度ASL

计算结果是3，就是平均3次比较可以查找成功

判定树还有一个性质

有n个结点的判定树的深度为log2n向下取整加1

观察判定树，因为每次折半都是正中

所以除了最下面一层，判定树是满二叉树

这点和完全二叉树是一样的

前面提到过，度量查找算法的效率

除了要考虑查找成功的效率

还要考虑查找失败的效率

看一下查找失败的情况

除了查找表中的11记录的关键字

查找其它给定值都是失败的

所以查找失败的给定值是无限的

根本不可能通过分析每个给定值计算查找失败的平均查找长度

我们的方法是把无限的给定值归类

观察图中绿色的方框，最左边绿色方框中是-1

其含义是把所有小于第1个位置关键字的失败的给定值归为一类

也就是所有小于5的给定值，都看做一类

1-2的含义是把比1大，比2小

这样失败的给定值归为一类

如果只考虑整数的话

失败的给定值应该是6，7，8，9，10，11，12

其它方框的情况类似，最右边的11-

是把失败的大于92的给定值归为一类

这样呢，就把失败的情形，归为了12类

我们考虑类的情况，就可以计算查找失败的平均查找长度

前面讨论对给定值28的失败查找

经过4次和关键字的比较

直到失败查找失败了

可以看出，绿色方框失败的比较次数是其双亲所在的层次数

那么12种失败情形中

有4种情形是三次比较直到失败失败

另外8种情形是4次比较直到失败

查找失败的平均查找长度ASL计算结果是11/3

不到4次一点

总结一下一般的情况

从刚才的判定树中，可以知道

查找成功的话，最多需要log2n向下取整加1次比较

而查找不成功，也不会超过log2n向下取整加1次

不失一般性

设有序表的长度n=2的h次方-1

这样，有序表，折半查找形成的判定树

是一颗深度为h的满二叉树

仍然假定每个元素查找的概率是相同的

因为每一层记录比较次数是一样的

按二叉树的性质，第j层有2j-1次方个记录

按层来累加

j从1到h，每层j呈2-1次方

结果是n加分之n+1，log2( n+1)-1 ，n比较大的时候

(n+1)/n接近1, 查找成功的平均查找长度是log2(n+1)-1

查找失败的平均查找长度是树高h，等于log2(n+1)

从分析结果看，很明显

折半查找的平均差的长度是一个对数阶的

基本就可以看做一个常数了

前面两节课

我们讨论了静态查找表中的顺序查找和折半查找

顺序查找的平均查找长度是线性阶

折半查找的查找效率非常高，是对数阶

当然要使用折半查找有两个前提

一个是顺序存储，一个是必须按关键字有序

作为静态查找表，没有插入和删除

对查找表进行一次排序

随后，使用高效的折半查找是非常合理有效的办法

但是，对于动态查找表来说，这就不太合适了

如果有频繁的插入和删除，对有序表来说

为了插入和删除后保持有序，需要大量的移动

或许这样的代价很大

抵消了甚至大大超出查找效率提高所获得的好处

那么折半查找就不合适用在动态查找表中

下一节我们讨论针对动态查找表的方法

好，同学们

这节课就讲到这

我们下次课再见