00:00
来看一段说明,比如说现在我有一个有序数组。同学们在学二分查找的时候,老师一定讲过,这个数组必须是有序才可以用二分查找,对吧?如果你是个无序的,你首先先先要把它排成一个有序的,比如说你用快排也好,规定排序也好,反正要快速的把它做成一个有序的,然后再去查找。你如果是个无序的二分查找,不,不能使用。对,如果你是无需的话,你只能是顺序操作,一个一个比,没有办法,那么我们就以这个为例,大家看我这里呢,有一个数组,呃,有个数组,这个数组呢是从小到大的。那么输入一个数,看看该数组是否存在此数,并求出它的下标,如果没有,就提示没有这个数。好,我们把二分法找快速的给大家写一下。好,我们打开。打开这个地方,我们新建一个包,叫search。
01:04
好,二分查找也是一个一个经典的考察内容哈,经常有面试官问你二分查找是怎么写出来的,我们就叫binary search。然后呢,这边写个object。好的,我写一个主方法,然后呢,前面这个数组我拿过来用用阿瑞。数组呢,我这里已经设计好了,我就直接拿来用一下。就不写了,好吧。好的,这边呢,我把它包一下。好,Barry包起来。包起来,那包起来过后呢,我们就开始来写一个二分查找的这个方法,那我就直接写了叫binary。Binary search。那么这个二分查找的思想在前面大家都知道了,我们现在返回一个下标,就用int,我先写第一种方式,就说说明如果。
02:05
如果存在。存在这个值。就返回就返回对应的下标。下标,否则返回一个负一,因为我们我们知道这个数组里面没有一个下标为负一的,就用负一来表示,找不到那二分查找怎么做呢?首先我们要把这个数组拿到。好,这边类型把它写进去int,然后同样道理,二分查找呢是从找到中间这个字,然后再进行这个比对,二分查图的思想,我们来回顾一下。二分查找的思想思路也可以啊,第一步。先找到中间值。先找到。找诶先找到中间这个值。中间这个值,然后呢比较,然后将中间值和和这个查找值。
03:09
查找值比较,那比较必然就有两种结果,哎,三种结果,第一种。啊,第一种就是啊,第一种就是相等,那相等当然你很高兴了,就找到了相等,如果相等就OK,那就找到了。那第二种情况呢,就是你这个查找的值啊,就就是这样说吧,你中间这个值大于。大于这个查找值,各位你就需要递归的,递归向哪,哪边查找向左还是向右呢。这个向左和向右要取决于你这个数组是从小到大还是。从大到小对吧。那不然的话,你这个你的你的这个前提就不好说了,假如我们现在是从小到大,你中间值大于这个查找值,那就应该是向左进行递归查找递归或者向向左。
04:07
因为左边数小嘛,向左进行递归查找没问题,那还有一种情况。还有一种情况就是你中间这个值,我们复制一份,中间这个值小于查到值,那说明你查到的值呢比你大,那就应该向右是意思吧,向右。进行递归查找。好,这就是他的一个基本思路。所以说我们看二分差的还是比较简单的,那比较简单,我们就开始来走了吧,那就写个left。你给我传一个左边的下标。右边的下标。还要你还要你给我传一个,你要查找是哪个词,就说比如叫find value。我们都以int为例,我们这个写完我要扩展啊,同学们待会儿呢,要动脑筋想一想。呃,根据刚才这个思路。
05:02
诶同学们,我们问大家什么情况下代表找不到呢。什么情况下会代表找不到所,所以说你你你们先看我把这个思路写完啊,我们这留了一个问题等待大家去解决,就是什么条件。在什么?什么情况下表示找不到?表示就就表示找不到了。好,我们先留留这个问题留在这儿,我们先把能写的写了,首先找中间值,找中间值对于我们来说应该是小儿科,我们先把中间这个下标找到。中间下标对于我们来说很简单,Mid index等于你传进的left加上这个right除以二。那当然有些同学老师这个除数来是个小数怎么办?这个无所谓啊,不管是它是,呃,这个向左边点右边一点都无所谓,他反正都全部扫描到,好先把中间这个索引找到,再把这个中间值就可以找到了,OK,那么这个中间词呢,我们可以这样写mid。
06:10
啊,Value。Value,我们就这样把它取出来吧,叫。然后把这个mid。中间值取出去,好,现在就开始比较,如果说如果说嗯,我这个按这个来走啊,我们先先把这个走完吧,如果说中间这个值。中间这个值。它大于。呃,中间这个值它大于你要查找的value流,那这个时候呢,就要向左。进行递归查找,怎么体现出向左进行递归查找呢?OK,就boundary,你要向左,数组不用变。你向左向左边走的话,那就说明你传进了这个left。不能变,对不对。啊,那么你中间这个幂的这个值应该怎么样减一。
07:05
对不对,然后泛的这个值继续往下传。就这个条件,一定要把它。呃,分析出来。OK,那如果说l if。Else if。那如果说我们这个中间这个值它小于范的value。啊,就是中间这个值它小于了。呃,中间这个值,那就应该向向右边,右边查找,OK,向右边查找这个条件呢,我们也把它写一下,那就是find value,那么宿主还是照写不误。那向后右面就应该mid。Index加一,然后R不变,这个R就是你这带过来的R,然后呢,这个find value继续往里面写。好的,呃,紧接着还有一个条件。
08:01
还有一个就是它既不大于又不小于,那当然就找到了,这个非常好,那我写一句话啊,就是找到。那找到你也不用,不用在这输出,直接把这个返回。把这个索引返回return,谁呢?Me index。好,同学们,这个条件这样写了,其实代码基本上就完成了。但这边有一个问题我们没有考虑找不到的情况。对吧,没有考虑找不到,那怎么样才表示找不到呢?找不到,我找一个同学说一下你你觉得应该是怎么样子的。找一位同学不找班长了啊,这次班长很很紧张,我们找一个同学随意的抽查一位同学吧,咱们叫做这个张超同学,在不在张超你哦,你就张超啊,我们找申康同学来,小申同学什么条件代表找不到呢?
09:01
这是什么情况下代表找不到呢,你感觉。就是你你能把这个找不到的条件分析出来吗。想不起来了是吧?啊,想不起来了是吧?溜号了,别别溜号啊,大家大家觉得这个数据结构没有用,那就错了啊,一定要认真听啊,我再找一个同学。王长成同学说一下。左边的边界值。边界值不应该是叫边界值,你应该是表示的索引吧。哎,对,是这个说明是不是这个意思,就是你这个L。怎么样了,它大于了,大于了R。是不是当这个条件一旦成立,就说明你是肯定找不到了,因为你你想想这个逻辑嘛,你是L不停的向右边跑,在变大。
10:02
但R呢,向左边跑再减小,但是当你这个左边。都大于右边了,那说明你已经把整个这个。全部都扫了一遍,但还没有。那你肯定是不行的,那等于这个条件是可以的啊,其实这个等于条件还可以进行一个比较,就是什么情况下呢,就刚好你找的数左右两边刚好顶到这一个值,它刚好相等,就是中间这个值好,所以说这门应该只是大于。大于的话,这个时候就代表找不到,找不到我们不用不用啰嗦了,直接返回一个负一。这个条件必须要有啊,如果没有这个条件,后面的结果是当你找不到的时候,它一定是个死循环,好,代码写完了,我们来调一下。啊,代码呢非常简单,我们来玩一把单,然后把数组放进去,然后咱们写一个零,当然。右边这个是N减去一个一。然后我们要找的数假设我们直接找边界值。
11:01
我们看看这个结果对不对。好,把这个索引拿到。我们进行一个判断。如果index不等于负一,那说明什么呢?哎,说明我们就找到了,就说找到。下标为。下标为多少呢?把这个加上就index。就可以了,否则我们就说明我们怎么样没有找到。就说没有找到。对吧,诶这快速的写一下啊。没有找到。没有找到,好,我们先来看看代码对还是不对。跑一个。好,我们执行完过后,我们发现呢,哎,其实是找到了。因为我这个一,呃,确确实实是下标为这个,我们再找一个边子是12341234呢,它是它最后这个数应该是下标为五。
12:03
OK,说明没问题,我们再找一个没有的,比如说我找一个负。1234的,它会提示一个什么呢?没有找到。大家看到没有正常,如果你把这个条件去掉了,你试下这个条件一定要去掉,肯定是个死循环。因为他一直不退出来,对吧,你看看,如果我把这个条件去掉,我们来执行一下。你把这个条件去掉过后,他在找不到的情况下,他就你看他他不退出。他就死在这儿。那肯定就有代码,肯定就有问题了,好,这个条件写完了过后,我们截取一段视频,这个就是我们所说的。
我来说两句