大家好
欢迎回来继续学习
C++程序设计
这一节我们来学习查找算法
所谓查找呢
就是从一个数据序列中
去找我们需要的元素
那么这个查找呢
又分成
你从一个完全无序的序列中
查找呢
还是从一个
已经有序的序列中查找
我们大家都知道
如果什么东西放的有序的
井井有条的
我们去找东西就容易 对吧
如果你把东西乱七八糟地堆放着
你翻什么都翻不出来
这是我们生活中的常识
那我们在程序中
写查找算法的时候也是这样
如果你要处理的数据序列
是完全无序的
那其实没什么好办法
一个个挨着找就是了
如果你要处理的数据序列
是一个已经有序的
那查找呢
就有好的办法了
首先我们来看
最笨的办法
就是顺序查找
如果我们遇到的序列
是一个完全没有排过序的
无序的序列
那我们从中查找
需要的元素的时候
那只好从首元素开始
一个一个一个依次比较
没有别的好办法
这就是顺序查找
下面呢我们来看
这是顺序查找的函数它的实现
这个非常简单
大家都会写
写一个循环
把数据序列中的全部元素
比较一遍
看有没有找得到
这种查找呢
当然你可能成功
也可能不成功
找到了就是查找成功
找不到那就是查找失败
说明这个数据里头没有这个元素
顺序查找
是一个非常简单的算法
这是一个
实现顺序查找的函数模板
它的参数接收一个T类型的数组
我们要查找的元素
在这个数组中查找
然后数组的元素个数
以及我们需要查找的这个关键字
也是T类型的
跟元素是一样类型的
那在这个for循环中
就是依次比较一遍
看是不是找得到
找到了就返回这个i
返回它的下标
那么如果是对基本类型的数据
进行查找的话呢
肯定是没有问题的
什么类型都可以
如果是对类的对象
数组进行查找的话
需要这个类重载过关系运算符
相等比较
如果
我们面临的要处理的这个序列
是一个已经排序好的序列
当然
我们就可以有更好的办法
不必用顺序查找了
现在呢
我来介绍一个既好用
写起来又简单的算法
就是二分法查找
也形象地叫做折半查找
如果说一个序列已经有序了
那我们要找一个数据的时候
就可以先取这个序列
中点位置的元素
看看到底我们要找的数据
比它大还是比它小啊
这样就可以每一次
使得我们要查找的范围缩小一半
这个过程呢
我们通过后面的图示来看
大家就会比较清楚了
现在我们来看
我们需要在这样一个数据序列中
去查找有没有值为21的元素
有的话它是第几个
把它给找出来
这个时候呢
我们就不必要从头到尾
去数一遍了
因为我们发现这个序列
它已经是由小到大
升序排列的了
所以呢我们首先呢
计算出这个序列的中点位置
那就是这里
我们用L表示最低下标
或者最低序号
用H表示最高的序号
那么它们两个加起来
除以2取整
就找到了中点位置
就是M现在指到的这个位置
经过比较呢
我们要找的这个21比56要小
所以从56开始
更大的那一半数据
肯定就可以立刻被排除了
我们不需要在那儿找了
那就只要从5到37这个范围去找
就可以了
这个时候我们就会把
最高下表H
移到第5个位置
移到指向37的这个位置
好 继续重复刚才这个步骤
再找到目前这个序列的中点位置
M指向了19这个元素
那现在比较一下
21比19大
所以从19开始往下的这一半
都排除掉了
我们不用在这里面找了
你看
查找范围又缩小了一半
接下来
仍然再找现在剩下的这个序列中
这一半它的中点位置
这个时候M计算出来
正好指向了值为21的这个元素
那一比较
正好是我们要找的数据
那么查找成功
它就找到了
那如果是找不到的情况
这个过程会是什么样的呢
我们来看
假设我们要在这个序列中
找值为20的元素
那前面的几个步骤都是一样的
到了最后这个地方
找到的最后一次的中点位置是21
但是我们要查找的元素呢
值是20
20比21小
这个时候
按照我们刚才的每一次
缩减一半规模的这样的一个规则
那么
指向最高下标的这个变量H
它就要挪到
比指向21的这个M
再小一个的位置
它挪到下标3的这个位置
现在这个问题出现了
L应该是指向较低下标的位置
较低的序号
H应该指向较高的序号
现在走到这个地步呢
H指向的这个序号
已经比L都低了
那就说明什么问题
说明整个系列
我们都查找过一遍了
找不到值为20的元素
这就说明这个序列中没有20
这就是查找失败的结果
下面我们就来看
用函数模板来实现
这个二分法查找的代码
这是一个二分法查找
也叫折半查找的函数模板
我们来看看
它是怎么样每次将查找范围
缩小一半的
这一个low初始状态为0
high初始状态为n-1
那么当low小于等于high的时候
就是我们还可以继续查找
这个数组里面的全部元素
还没有查找完的时候
这时候找到它中间位置
low+high除以2取整
然后它中间位置的下标
比较是不是
等于我们要找的这个数
如果等于
返回就行了 找到了
不然的话呢
它要继续查找
这个时候如果key
小于等于中间这个元素
那么更高的一半
就不用再找了
直接把high下标
移动到mid-1就可以了
如果是key大于这个中间元素
那么就把low下标
移到mid+1就可以了
那么就如此循环
只要low小于等于high
就继续找
如果找到了
在中间就会执行return语句
把找到的这个元素的下标
就返回了
如果退出了这个while循环
就说明因为low大于high了
那么状态就是没找到
这时候返回一个-1
表示没有找到