00:00
同学们,我们下面来看一下二分查找算法。那二分查找它是一个什么意思呢?首先我们要明确一点,二分查找它是要求是在一个有序数组中才可以去使用的,这种查找算法什么意思?就说如果你这个序列是没有顺序的。所以有序事代表你可以是从小到大,也可以是从大到小,但是你不能是无序的,就如果是一个无序数组,你要使用二分查找呢,需要先把它。进行一个排序,做成一个有序数组,过后再进行二分查找,明白意思吧。好,那么我们来看一个小案例,这边案例呢,还是这么一个数组,这是个有序的,看到没有,然后呢,我输入一个数,查看数组是否存在指数,并求出下标,如果没有就提示没有这个数。好,同学们,这个呢,我们会使用到递归。呃,二分查找有两种,一种是递归查找,一种是非递归,非递归呢,我们后面再讲好吧,那现在呢,我们先来对二分查找的一个思想进行一个分析,来各位朋友先来给大家聊一聊二分查找的这个思路。
01:16
对不对?好,我先把思路给大家聊一聊。二位老师是什么意思呢?各位同学看我的这么一个思路。我先把思路给各位朋友板书到这里。大家注意听哈,就是二分查找的,二分查找的一个思路分析。二分查找的一个思路分析,嗯,他是这样子第啊这样子啊,第一步第一步首先首先确定,首先确定该数组,该数组中间的中间的这个下标。比如说我们中间的下标是mid,它等于什么呢?它等于na这个下标,加上我们right这个下标,然后除以二。
02:03
OK,然后干什么呢,然后让。呃,然后让这个,让这个要查找的数就是。你然后让需要。需要查找的这个数。比如说这个数是你要找的啊,叫find value,和谁比较呢?和这一个me的这个比较,那比较当然就有这么几个可能性了,呃,第一种呢,就是这样一个,如果find value它大于了R。这说明什么问题?说明什么呢?呃,当然我我们现在假定这个数组是从小到大的啊,大家看我数组是从小到大的,因为你这个顺序决定将来是到哪去找,这也是有关系的,如果你这个find value大于me,说明什么呢?说明你要查找的数,说明你要查找的数在哪里呢?在密的。
03:06
的哪边。在密的哪边你大于别人,所以说你在密的这边,这个的右边。因此,因此,因此需要递归的,递归的向哪里呢?向右。这个进行查找。哎,是不是向右查找,因为呃,你你要查找的数比我中间那个数大嘛,而我又是从小到大,显然你你要查的数只能在右边去找。是不是?那反过来同学们看2.2,如果find value它小于二米,说明什么问题呢?OK,说明你你要找的数小于中间数,说明我就复制一份,说明你要查找的数应该是在幂的,幂的这个这个索引的哪边呢左边。是不是左边呢。左右大家要分清楚,因此需要递归的向左查询。
04:04
向左查询。那么还有一种可能性是什么呢?就是2.2.3 2.3就是你很幸运,就是find value,它等于了r me,说明什么问题啊,说明你找到了,说明找到,找到就返回。找到就返回,那么这里面还有一个问题,同学们有没有发现,就是我们二分查找里面使用使用到的递归。那递归我们在前面讲过,递归有一个特别重要的规则,就一定要有一个退出递归的条件。那么请思考什么时候,什么时候我们。需要,需要,需要结束。结束这个递归呢。大家知不知道,第一种肯定是我们找到了。我们就。就结束递归,这是这是正常正常的第一种就是找到。
05:00
找到就。就结束递归,这是肯定的。呃,比如说我们第三种情况,找到就结束就返回了,那还有一种情况就是找不到是不是你就说你你把整个把整个数字都走了一圈,发现你找不到,是不是也要结束递归啊。那么就说就是便利完了,便利就是就是递归完整个。递归完整个数组仍然然没有找到这个find value是不是也需要,也需要结束递归?那么这个条件应该是什么条件呢?同学们分析的出来吗?这个条件就应该是你的nap的这个索引和right这个索引。它的这个条件发生变化,也就是说应该是当什么条件呢?当我们的这一个right。或者这么说吧。当我们的left。当left大于了right,就需要。
06:01
就需要退出了,也也就说当这个ne大于了right,说明你你你这个就没法玩了,你打个比方。比如说我们第一个数是定位在中间89。假设定位在,呃,应该是十啊,应该是十,那假如我们现在要找的数是,呃,假如我们要找的数是什么呢?呃,比比如说我们要查找的数是。是这个,呃。多少呢,负一。那是不是负一跟11比较,我们发现你这个find的value是小于它的,是不是我应该向左边去找,但是到左边还是找不到,但找不到你不停的往下走,走走走两两头嘛,相当于说你你中间你你你这边有一个索引,是指向数组的最左边的,你这边还有一个索引。
07:00
最初的时候是不是这两边有索引,那么中间这个索引是零,你看012345,那么就是零加五除以二,是不是中间是一个一比较,哎,你要找到负一在这边,于是乎我应该怎么办呢?我应该把这个。挪到这边来,是不是在这地方我们右像刚才一个逻辑比对,但是这两个这两个指针它不停的左边的向右,左边就是left向右边移动,Right向左边移动,如果当某个条件满足,就是left还大于right,是不是就意味着我们找不到了,因为你最终不停的最终最终最差的情况就是他们重合了。重合如何判断还不行,那是不是这个还继续往这边移动,而这边往这边移动,那这个时候就造成了你原先这个na还大于了这个right值,这个时候就应该退出了,明白吗?我不知道说清楚没有,大家大家应该很好理解啊好,现在我把这个代码,呃,思路已经已经说清楚了,同学们我觉得应该也很好理解,对不对,就是这个条件就是代表什么呢?我们就真的找不到了。
08:06
那这个你不停的往下地位地位发现耐的都大于right了,你还找。那就永远找不到。所以说这就是我们二分查找的一个思路分析,我截取一段视频,下面呢,我们准备代码实现。
我来说两句