当前课程知识点:数据结构 > 第7章 查找 > 7.2 静态查找表 > 讲解(下)
下面,我们介绍第二类查找算法,折半查找
对于那些关键字有序
并且是以顺序存储方式存储的查找表
我们可以采用折半查找,折半查找
也称为二分查找
我们来看它的查找思想
首先,k与表的中间位置
注意,是中间位置
而不是中间值,是位置居中
那个元素mid的关键字,进行比较
如果k小于中间位置的值
那如果k存在的话
一定位于左半区间
所以,我们继续在左半区间找
当然
假定关键字,是按照从小到大排列的
如果k大于中间位置的关键字
k如果存在,一定位于右半区间
这样,每次在找的过程当中
我们就把下一次要找的区间
要找的元素个数,减小了一半
所以叫折半查找
重复以上步骤
直到
关键字k和中间位置那个元素
它的关键字相等
这时候
就说明查找成功,元素就在中间位置mid
这个位置上
那什么时候
上面这个过程退出呢
或者说,查找失败呢
就是区间无任何元素
我们要找的那一半区间,不断地缩小
最后,区间长度为0
甚至是负值
这时候,说明关键字k肯定是不存在的
其实,折半查找就是我们平常所用的翻书的策略
大家想一下,我们平时翻一本书
比如,要你翻到100页
你都是按照书的总厚度,往中间一翻,发现是200页
100是小于200的
然后,你在前200页里面
再衡量一个中间的厚度
再一翻,一直重复刚才的过程
直到你翻到的那一页,就是要找的100页
现在,我们通过一个例子来说明,我们在一个长度为11的
并且关键字是递增排列的
表当中去找
因为
我要计算元素的中间位置
既然有中间位置
实际上,是暗含了一个条件(元素是以顺序方式存储的)
换句话说
你要采用折半查找
必须满足两个条件
第一个,是关键字有序
第二个,是元素以顺序方式存储
现在,我们要找的关键字
是13
我们计算出中间位置
这个很简单,拿区间的下界
加上上界,除以2,就行了
那么,中间位置应该是1加11
除2,是6,拿中间位置的56,跟13进行比较
13如果存在,一定位于左半区间
这时候,我们把要查找的区间上界
改成37,就可以了
之所以没有放到56的后面
这是因为,13跟56既然不相等
那我们就把区间在一半的位置,再减一个1
所以,我们把区间的上界,改到了56的左边
再重新计算中间位置,应该是1加5,除2,是3
那么,13是小于19的
如果存在,一定位于19的左半区间内,继续修改上界
修改成13,再计算中间位置,1加2,除2,注意整数相除,向下取整,是1
中间位置的元素是5,13大于5,13如果存在
一定位于这个区间的右半区间
所以,我们把区间的下界,改成5后面的那个元素
也就是13,继续刚才的过程,这时候,区间仅仅包含一个元素
中间位置
就是2加2
除2,还是2
这时候,中间位置的元素,就是等于要找的k(13)
说明查找成功,返回这个位置,就可以了
现在,我们找一个不存在的元素
比如85,同样,计算中间位置
1加11,除2
是6
那么,85是大于56的
如果存在,一定位于右半区间
所以,我们修改区间的下界,改成64
再计算中间位置
7加11,除2
应该是9
85是大于80的
如果存在,一定位于右半区间
再计算中间位置
10加11除2,是10,85是小于88的
如果存在,一定位于左半区间
那么,修改上界,修改成88左边的
现在,大家注意到,区间的下界大于区间的上界,也就是区间为负了
这时候,我们就没有必要再向下找了
因为,要找的区间已经为负了,它不包含任何的元素
这时候,就说明查找不成功
现在,我们给出完整的折半查找的算法
在静态查找表ST当中,去找关键字为k的记录
我们返回的是,那个记录在查找表当中的位序
这里为了描述区间的上、下界,以及中间位置
我们给定了3个变量,low代表区间下界,high代表区间上界
它们的初始值,分别是第1个元素和第n个元素
然后,mid代表中间位置
只有当low小于等于high的时候
也就是,要找的区间
至少包含一个元素的时候
我们才有必要重复刚才的步骤
首先,计算mid
下届加上界,整除2
如果要找的k,是小于mid位置的元素的时候
这时候,我们直接将上界,改为mid左边的那个元素的位置,也就是mid减1
以便在左半区间继续找
else,如果是大于
k如果存在
一定是位于右半区间
我们将区间的下界,改成mid右边的那个位置
也就是mid加1
最后一个else
说明是相等的
相等的时候,直接返回mid
这个循环结束的时候
说明,low是大于high的
这时候,区间为负
直接返回0
我们用0,来表示找不到
现在,我们来分析一下
折半查找它的性能
我们每次将当前查找表,一分为二
分成两个子表
这时候,可以用前面讲的二叉树来描述,这时候的二叉树
我们通常称为判定树
比如刚才,我们去找
13
树的根56,就是长度为11的那个序列
当中的中间位置,也就是第6个元素
然后,它的左子树,就是左半区间的元素构成的
右子树,就是右半区间构成的
同样,左半区间
如果我们再一分为二
那么,中间位置的值是19,右半区间再一分为二
中间位置的值是80,继续往下分
直到区间仅仅包含一个元素,或者为负
现在,我们来看查找成功的时候,k=13的时候,实际上,一共经历了4次比较
也就是,从二叉树的根,走到相应结点的过程
你看
我们找13,先比较56,再比较左半区间中间位置的19,继续比较
继续比较,找到了13,经历了4次比较
这时候,也就是查找成功的时候,比较次数
就是结点所在的层次
查找不成功呢,我们看红色的箭头
比如,找这个85
同样,也要从根结点56开始
因为85>56
一定位于右子树上
85>80,一定位于右子树上,85<88,如果85存在
一定位于88的左子树上
现在,88的左子树为空
没有左孩子
这时候,就说明查找不成功
它也是从根结点,走到某一个结点
假设,树的高度是h
通过前面的分析
我们总是将序列一分为二
左序列和右序列再一分为二
最后你会发现,这棵树的高度
实际上,跟我们前面讲的完全二叉树,有点类似
它的高度,就是log2(n)向下取整,加1
我们找56,只经历1次比较
找19和80,经历2次比较
找5、21、64、88
经历了3次比较
最后,我们把每一个结点经历的比较次数,求一个平均值
最后就是这样
由于时间的关系
具体推导,在本章结束的时候
在讨论里面,我们将会详细地给出推导过程
当n比较大的时候
这个(n+1)/n,就约等于1
所以,折半查找它的平均查找长度,就是log2(n+1)-1
现在,我们来看第三种静态查找表,索引顺序表
索引顺序表又叫分块有序的查找表
所谓分块有序,就是块内无序、块间有序
比如,我们看这样一个包含18个元素的查找表
尽管这18个元素总体上看,是无序的
但是通过观察,我们会发现
如果我们把这18个元素,分成3块
1到6一块
7到12一块
13到18一块
这3块之间,却是有序的
比如,第2块当中,6个关键字,都是大于第1块的
而第3块,6个关键字,都是大于第2块的
这就叫块间有序
但是3块各自内部,却是无序的
这时候
我们很容易想到,可以综合前面讲的顺序查找
和折半查找
为了能够采用折半查找
我们必须存放每一块的索引
也就是,记录每一块它的起始位置,以及该块的最大关键字
这两个信息合起来,叫做索引
index
比如第一块,起始下标1,和最大关键字22
我们记录下来
这是第一块的索引
第三块,起始下标13
最大关键字86,记录下来
作为第三块的索引
第二块也是类似的
我们会发现
所有的索引
它们构成了一个有序表
而且,我们是以顺序方式,来存放每一块的索引
现在,元素有序
而且是以顺序方式存放的
我们马上想到采用折半查找,来查找索引表
因为折半查找,它的时间复杂度是对数级的,它是高于顺序查找的线性级的时间复杂度
如果我们给定了一个关键字k
假设,它等于24
通过在索引表当中采用折半查找,因为22<24
并且24<48
我们就可以确定
24如果存在,一定位于第二块
因为,第一块的最大关键字是22
我们找到第二块的起始位置
然后,从7开始
因为块内无序
我们只能采用顺序查找
去逐个地找
直到找到24
如果找不存在的
比如找30
那也是一样的
直到找到第二块最后一个元素,都没有找到30
说明30不存在
这是在块的内部采用顺序查找
综上所述
索引顺序表,可以综合采用前面的顺序查找和折半查找
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解(上)
--讲解(下)
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解(上)
--讲解(下)
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解(上)
--讲解(中)
--讲解(下)
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解(上)
--讲解(中)
--讲解(下)
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解(上)
--讲解(下)
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解(上)
--讲解(下)
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解(上)
--讲解(下)
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解(上)
--讲解(下)
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解(上)
--讲解(下)
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解(上)
--讲解(下)
--作业
-6.3 遍历
--讲解(上)
--讲解(下)
--作业
-6.4 最小生成树
--讲解(上)
--讲解(下)
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解(上)
--讲解(下)
--作业
-7.3 二叉排序树
--讲解(上)
--讲解(下)
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解(上)
--讲解(下)
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解(上)
--讲解(下)
--作业
-8.3 交换排序
--讲解(上)
--讲解(下)
--作业
-8.4 选择排序
--讲解(上)
--讲解(中)
--讲解(下)
--作业
-8.5 归并排序
--讲解
--作业
-讨论