00:00
该怎么写?同学们看,我把这个题打开。而同学们看,现在这个数组变成这个样子了,当一个有序数组中有多个相同数值时。将所有的数字都查找到,比如我这里有两个1000。大家看在我目前这个情况下,如果我在这儿加一个1000。那么我在这里面也写,我要查找1000。其实同学们都很清晰的知道,他只会返回一个结果。他返回的是哪,赢了下标为五的这个。啊,至于它为什么5V5大,要取决于你在这个经常进行二分差的时候,他刚好找到了一个了,就不停的分嘛,刚好就找到这个了。那现在我的问题是。我要把所有的所有的都查找到。同学们有思路吗?我找一个同学,你们先想一分钟。
01:00
那我找一个同学说思路我来实现。先想一分钟啊,每个同学都想一想。我们找一个同学来说一说他有没有什么思路啊,我就随机抽查了啊,呃,找一位同学叫做张宏文同学来说一下有思路没有。啊,转班去了是吧,再找一个东西叫王静。就你吧,嗯,有思路吗?王静同学。我先通过这。嗯。用这个值和。应该有问题了,他说便利那就麻烦了,那便利呢,就相当于说这个二分就没有意义了,对吧。是我知道,但是你便利你你你你不知道什么时候结束,你只能全部变完了,比如说这有两个,那那我那你怎么敢保证后面没有一些,你只能全部变完,所以刚才那个可能他大体知道这个意思表述不是很好,那这这位同学你来回答一下来。
02:16
那那个。找到找到这个数之后。那边看一下。往右边就是找到这个数,不管是哪个数向右边探,那左边也有可能有啊。就就左右都得探是一是吧。啊,那碳的时候这个条件是什么呢。停止。哦,不相等就停止了,那你说是不是相当于说这个地方代码应该是在这个else这个地方想办法处理。就在返回之前想办法把这个,因为这个你找到了,先不要返回,然后向左边和向右边进行这个检索,然后把这个相同的这个地方扔,扔给他的一个数组。
03:03
放回一个圆组或者放回一个buffer都可以是吧?好,大体的思路应该是没问题的,我们把这个代码实现啊,好老师呢,就把这个代码给大家实现一把。好,我们我们把这个代码给大家走一遍来。刚才这个同学这个大体的思路没有问题,我们现在呢,来考虑一个新的情况,那我不动这个binary research,我写一个binary search2。说你们在写代码的时候,不要轻易的把原先代码删掉啊,你们以后参加工作以后不要建议不要轻的把人家的代码干掉,到时候你找找不过来哭的地方都没有说,尽量你自己单写一份给他分开就行了。现在呢,我们要考虑的是这样子的。处理。我把这个需求拿过来,我就不写了,好吧。这个这个需求我们先给大家放到这,大家看老师怎么去实现它。首先我们分析一下。
04:01
分析刚才呃,同学已经说的很很很清晰了啊,分析就说在哪里呢,第一个我们返回的这个结果。返回的结果是一个数组,但是这个数组还不行,还必须是一个可变数组。大家知道为什么必须可变吗?因为你不知道掉有几个几几个结果,因为数字大家都知道,创建起来它必须指定大小,对吧,你是指定十个还是二个不知道,所以说是可变速度,那就应该是2A。Buffer。学过这个。好第二个,那你在找到这个数的时候,应该向它的前边或者叫左边扫一下。然后再向右边扫一下。对,那就说在找到在哪里呢?在找到结果时。像。向哪里呢?向前面向左边扫描。
05:03
也要向右边扫描。向右边扫描。啊,扫扫描这个扫描的退出的前提是如果发现。有一个不相等就可以退出了,但是还有一个条件就是你在扫的时候呢。你在扫的时候,你还要判断这个下标是不是合理的,对吧,因为有一种可能性是这样子的,同学们。有种可能性是这样子的,我我这里面全是一全是1000。有没有这种可能性呢?有,所以说你你不能说我找到一个就退,因为你还得这个退出的条件,待会是要同学们好好去想的,这个条件是什么,待会我看。好,当找到结果后。找到结果后。就。就加入。到哪里呢?A buffer。好,各位同学,代码的思路咱就分析完了,那同学们首先代码应该在这在这加,在这加,先不要着急返回。
06:05
先不要着急返回。OK,这个地方首先我们定义一个。我们先定义一个可变数组,定义一个可变数组,因为你在做开发的时候,完全有可能遇到这个问题,对吧,你你人家有序数组。不是说完全是。就不能重复数据吗?那定义一个可变数组,那这个太简单了,我们在前面呢,已然学过,我们就叫R,就叫结果吧,结果这个这个R。然后呢,呃,可变数组是怎么怎么写出来的呀。是不是写个array?八份BUBFFL,然后。这个地方是不是还是要写一个类型的。没没问题吧,现在它的大小是不是愣是是零。是你好,现在呢,我先向里边扫呢,向左边扫。
07:01
左边少。在左边扫描应该怎么扫?通常扫描应该是一个外循环。所以你的条件应该是这样子,不用管,先试醋,先扫一把。我一直扫,什么时候条件满足退出呢,如果。如果,呃,当然你这个密的index不能动。对不对,所以说你把这个midex先用一用,因为mid mid的index是我们的一个基准,所以说你来设计一个T,或者叫做呃一个一个扫描的一呃一个值,我们这样子来做一下。设计一个这个值,比如说这个呢,就是我们的temp。它等于me。减向左边扫的话,同学们它最大那个应该是几啊,是减一呀。是是这意思吧,好减一,那什么条件我就退出了呢,就这样子的,如果。啊,就说如果temp。
08:01
如果这个,呃。哦,我们想一想啊,如果temp只要他。嗯,这样子啊,呃,如果它小于了零。小于了零或者或者。或者什么呢?或者你找到这个R。对应的这个temp,它不再等于你的这一个find value。各位,是不是只要这里面有一个条件,就代表我们没有必要再少了?这个能理解吗?应该能理解啊,Break。OK。那你在这个衣服做完了以后,是不是你还要判断。这个值是不是跟你这个插头是相等的,因为你找到地方,它可能前面就刚好是一个,所以说你这边再加一个条件。If看清楚了,就是说你的如果这个every。它等于了。它等于你这个find value。
09:02
然后你就做一件什么事情呢,把它扔到。你的。把这个数这个索引扔到我们这个可变啊数组里面去,那这个就是temp。但是你这个做完了以后,你不能退出,为什么不能退出,因为有可能人家还有。这不,他左边可能还有一个呀,所以说你这边还得做件什么事情呢?Temp减等于一看懂吗。好,这样子这个条件就能不停的这样去做。OK,好,那现在呢,我们呃,就可以这样来写,那么把它BREAK1把。Break,好,各位同学,现在呢,我把它包起来。包起来过后,前面一样的道理,我们给它整一个这样的ut.ctrl.breaks。点效性。好像这种像这种小的技巧,大家要啊,经常多写写啊,比如这个什么怎么去左右扫描啊,这个我相信同学们要去多写一下,这个就是向左边扫描,左边扫描以后,我们现在呢,为了保证这个顺序大致相同,我们就把中间这个直线加进去,再向右边扫,这就保证基本能基本上能保证就是我们索引的这个顺序也是也是一样的,对吧,那这样就比较好,现在呢,我们把中间这个也加进去。
10:19
啊,将中间中间这个索引。也加入。所以加入好这个代码就很简单了,我们把这个代码往这一写,把当前这个密index。放进去,但这个还没有完。因为你还得向右边扫,所以右边也有可能还有啊。向右边,右边。右边扫描向右。向右边扫。那像页面扫描这个思路几乎是相同,但是呢,注意啊,要改。你这个temp。是不是要在幂的这个基础上加一啊?
11:03
因为你身向右边跑嘛。向右面扫,那同样道理,你这个while语句我们拿下来。拿下来过后哪地方改一改,同学们。这个地方肯定要改,要如如果它大于了谁呀。它大于了我们这个数组的点认识。呃。不是大于等于。它不等不等于这个呀,不不能不不能说是不等于啊,那不等于,那不行,它只要如果它增幅不停在涨嘛,它到时向右边扫描更是他不定涨,它如果是大于了,我们这个嫩是减一是不是就不能再跑了。是吧,那如当然这个条件还是一样的。如果这个条件满足就退出来了,退出来过后如果相等,就把它加进去。同时这个要变成。加一看懂吗。这个这个肯定是加一嘛,你加不停的加嘛,我因为你是向右面扫,右面扫这个大家想一想,那个值肯定是在不停的涨,好最后我们要返回的这个结果就是我们的哪一个呢,就是RV。
12:11
这个东西。返回那返回。这儿写个return。啊,返回现在这个错误的原因是因为我们这个方法这写的是int,它肯定是不行的,我们直接写buffer,把这个类型写进去。好,当然你这样写了过后还有问题,问题是在于,呃,你我把这个换换一行啊,这个因为太多了啊,这个地方看起来有点难受。好,这边因为你这个负一不能转成奥buffer,那这个时候呢,也很简单,你就返回一个空的奥buffer,刚好我们可以通过它的大小来判断到底有没有结果。是不是?好,这样代码是不是,诶这还有问题。还有问题,是哪里出了问题?同学们看出来了吗?
13:03
哪地没改名,是不是你还调动better啊?是这个地方你掉的是应该掉几了,该掉二了啊各位同学。是不是好,这个代码就写完了。啊,蛋白体吗?我们来测一下吧,同学们,我们来测一下,那现在呢,我们把它改成第二种方法,第一种方法我们知道是,呃,肯定是找不出来的,那第二种方法我们来玩一把。那大大家看一下啊,第二个方法,我们接受的这个结果呢,就是一个array。对,然后b search2把A放进去,然后呢,零不变r.NS然后这边啊得减一,然后呢,我们找1000。好找1000,然后下边我们就判断,如果这个认识它不等于零,说明什么有。说明找到了A,要是如果它等于零。那说明什么呀,没有找到。
14:01
这个逻辑还是很清晰的,那找到的话,是不是你应该把它遍历出来,看看索引到底有哪些好,我们就遍历一下。有哪些呢?Index走。All right。好,同学们,我们来跑一把。各位同学。那么我们找到一个什么?找到的索引有?索引有哪些啊,我们把它打出来就是index。好同学们,现在我们再来看看结果对不对,我现在有两个,有两个一个是这个,一个这个我们运行一下。能不能找到朋友啊?你看一个是四,一个是五就找到了。就找到两个都找到,那我问大家一个问题啊,呃,你们有没有发现他会出这个问题,这个问题呢,我留给你们去解决啊,1000我有四个。呃,我我先问大家一个问题,四个是不是都能找到,这个大家不用怀疑吧。但是你们会发现很奇怪,就是说他这个打出索引不一定是有序的。
15:02
大家知道为什么吗?那我跑一下你看。你看这四个肯定都找到了,这是没问题的,456诶怎么还真是有序的呢,不对,他就不应该是有序的,他有可能没有序啊,我为什么这么说啊,我再看一下。我我知道,但是应该。诶,怎么都是有虚的呢,不对不对,是这样子的啊。因为我你们想啊,按理说他不一定是有序的,因为你看我这往左边找的时候,假设左边有两个,是不是先把后面这个加进去的呀。是不是啊?主要是在右边的。这个不应该呀,我看看为什么这么诡异啊。他是不是刚好就找到最后这一个了,我我再来一个看看。这个跟我想的怎么不一样呢,他应该有可能不去啊。这么稳定吗?嘿,你看啊,你听我,你听我分析,你听我分析啊,同学们听我分析,假设我们找的是这个。
16:07
是不是假设找到这个吧,这个这个是一个位置,那那我向左边扫的时候,是不是我先找到它了。先把它找到,是不是我我先把这个索引加去的呀。是不是假,假设这个是012345,是不是先把五加到这个。这个buffer里面去了,然后再扫描是不是四啊。是按理说他用一个有可能是打出来一个五四,然后是中间这个值啊。是不是按理说有可能出现这个无序的,为什么这么稳定呢?在这边加一个是吧。把89删了。把89我删一个哈。这个案例说有可能出现无序的,居然这么稳定啊,怪事。345678这么稳定不对呀。
17:00
这个怎么,那我看一下这个密到底是谁,这个密一定,如果是这样的话,密一定每次都到最后这个。我们来试一下这个密到底是谁?我我是不是没掉啊,掉的是这个啊,我把这个密打一下。是不是在这打一下这个密。在返回之前我们来研究一下啊,在这我们找一下这个密。密的。Index。等于他每次都找最后这个,我们来看一下找一个好,他可能是每次都找到最后这个了八。哦,应该是四四的话,他刚好就把四找到,所以说四找到,四找的话,前面三一个好,我我我们再再加一个。再加一个,多加几个,我不相信这么稳定啊,诶,我那个数据上哪去了。我我多整一个,我只狠点干脆啊。我下这么多,我看他。还能这么问你吗?诶你看这个就不对了吧,诶你看是吧,这韩老师还是对的吧,54367,你看这个地方它确实是有序,就因为你后面的时候,它是它是从后从从这个前面往往上走嘛,但是你你像前面加的时候,就是比如你找到这个六了,找六了六,你你找的时候是不是先把五加进去的。
18:23
然后再加的四,再加的三,所以他会这样子来走,那这个地方能不能解决呢?其实也特别好解决啊,特别好,因为大家都知道我们我们这个。我我们这个就是这个数组啊,本身它就支持他就支持这个sort是吧?哎,他就直接sort一下排序,大家可回忆一下我们怎么排的啊,我把这个改成R。啊,排序的时候是不是它会让我们传入一个函数啊,大家看你你你们看啊传输传入一个函数,看这个浮动的。那么我我们回忆一下怎么写的,是不是按我们以前写的是个int,然后这边把这个X1写,它默认就按照你这个这个返回的值进行排序了,好这个应该默认就是从小到大这个就稳定了。
19:09
因为我这个再打应该就是稳定的,诶这个没排完呢。哦,是不是要收一下呀,你你排完了过后,你是不是要把它重新重新接收一下才行吧。因为本身排序并不对它进行改变,好搜一下就可以了,来各位同学。请看代码。诶,现在是不是就可可有序了呀,可以的啊好同学们,那关于这一个二分的二分的一个小扩展,老师就给大家讲到这,那如果同学们在遇到这种类似的问题的时候,可以用这种思路来解决好,那我们把这个代码稍微的给大家整理一下。那刚才呢,我们讲了一个课后思考题。各位。课后四道题我讲的是一个什么呢?就是扩展了一下啊,代码如下。
20:01
代码如下,新的代码啊,新版的代码。新。啊。新版的代码如下,好的,我给大家,呃,放到这里来。就是说有些有些问题啊,就是要同学们自己去实际的呃解决。好,把它放好。好,关于二分,我们就讲到这里。
我来说两句