00:00
下面我们来看二分查找的一个课后思考题,这个课后思考题是这样子的,同学们看,他说当一个有序数组中有相同的数值时,如何将所有的数值都查到?比如这里有两个1000,那么我们来看看,如果有两个1000,此时此刻我们能返回的其实也只有一个,对不对?你看我写了一,再写一个1000。那么我们运行一下,你会发现它返回的呢,是一是负一啊改一个。改成1000运行值,我们发现它找到是下边为五的这一个,1000及哪一个呢?这个1000。那么还有一个1000你没找到。所以说现在呢,我们有个需求是要求当。这个数组里面有多少个,我们全部找到,比如说你这有三个四个,我全部都需要找到。三个。再来一个,我需要全部找到。也就是说我找1000,我不说找到一个就完了,我要把所有的。
01:02
1000全部找到。并且返回到下标。对不对,好,现在呢,我们这样子来做,我不在原先这上改,我们直接写一个新的来,各位同学。好,现在呢,我们完成一个课后,完成一个课后。课后思考题。思考题,这个思考题的要求呢,它非常的简单,非常简单,我们把需求给各位朋友拿过来。大家可以看到,要求就在这里。那既然有这个要求呢,我们就来分析一把,然后把它做完,首先我们不需要重新写一遍,其实大家有有没有发现,我们只要在哪个地方做处理就行了,是不是在这个地方。因为你在这向右递归,这向左递归,最终你发现你找到了,但是在找到密的时候呢,你先不要返回一个int,你是不是需要在这个need,以need为中间线向左扫描和右向右扫描,然后把所有的索引加到一个集合里面去就可以了。
02:10
是不是这意思?好,现在我做一个思路分析。我的思路是这个样子的,同学们听我说啊,我们先说思路,再说代码第一步。在。找到找到密的知识。只是不要马上返回。不要马上返回。怎么办呢?我们需要这时。这是先可以可以让啊向。像什么呢?像密的这个密的这个索引。啊,这个密是索引值对不对,因为它代表的是索引。呃,向幂的索引值,索引值的什么呀,左边左边扫描。扫描。干什么呢?将所有所有满足,满足查找值的满足这个1000的吧,我们说具体一点,满足1000的这个元素的下标的元素的下标。
03:14
干什么呢?加入到加入到一个集合中。比如说这个集合呢,我们是r list的。问题吧,那把这个做完了以后,是不是我们还要向密的索引值的,哎,索引。值的右边。右边扫描。呃,右边扫描。那右边右边扫描干什么呢?将所有满足1000的下边元素也放到RVC集合中。最后我们将这个返回,最后将什么呢?将。将这个list返回就可以了。是这意思吧,同学们,那就说我们其实只要在这加东西就行了,其他不要动,来吧,同学们把这个拿过来,拿过来过后呢,我们把这个代码往这拷贝一把,拷贝过后我把这个改成二。
04:10
返回的时候呢,我们不要再返回一个int了,而是返回一个r list。List,好,那呃,A list我们先写到这啊,先写到这list这面我们需要呃,引个包包。引一个包包好引进去就可以了。二那下面这个代码呢,我们在这玩玩一把,什么意思,就是把刚才这个思路在这执行一下。是不是把这个思路分析我们这走走一走就可以了,来把代码写到这来。把代码写到这里来。嗯,首先呢,我们先创建一个,各位同学,我们先创建一个r list,怎么写呢,非常简单,又一个r list,我们这里面放的是integer。是吧,下边是个整数吗?我们让它用自动装箱的功能放,放到这个二维历史里面去,然后这边接收一下。
05:03
List,然后呢是呃,In,然后list等于好,这边我们叫做resultex list,这样比较简洁,好这边我们也需要营销包。引进去。历史的。好,先不要返回了,先不要返回,那我们先干什么呢?向左边扫描什么,先这个向左边扫描呢。各位同学怎么实现向左边扫描呢?非常的简单,大家想啊,你做一个临时的一个词,比如说int temp。等于谁呀,谁等于这个幂减一。是me的减一,就是我们中间这个索引向左边,向左边去的第一个,那这个时候呢,我们用一个Y循环。我洗个醋。我怎么找啊,同学们看啊,如果temp在。
06:02
如果tempb小于零了。如果temp小于零,或者看,或者注意听这句话,看看能不能理解,好吧,或者我们。里面的这个temp,它不等于我们要找的值说明什么问题?说明什么问题?说明我在向右扫,向左扫描的过程中。已经需要退出了,因为如果是小于零,说明你已经扫描到左边最最左边了,如果这个条件成立了,说明什么?说明你找你在这个便利过程中发现了有一个不等于find value你就可以退出了。是不是这就可以退出?那这个退出我们就break就搞定。Breaker就搞定,那否则我应该怎么办呢?否则否则,诶否则就干什么呀,就把这个temp放入到集合中。
07:06
放到哪个里面去,放入到这个集合中,是不是这意思,那代码写一下就可以了,list.add。把谁放进去啊,Temp放进去,这里我们用到了一个自动装箱功能,然后temp往左边移动一下。Temp主义。主义。是不是这样子的,同学们,那这个做完了以后,他。这个向左扫描工作就做完了,做完不要忘了这件事情,我们还要把中间这一个,你本身找到中间这个密先放进去,也就是说把左边的扫描,把左边的处理了,再放中间的。这是中间的这找一,现在刚刚找到这个密嘛,啊放入现在呢,我们还要向。Mid的索引的右边扫描试一试吧,同学们,因为你有可能在右边呢,右边是不是跟刚才这个思路很像,然后temp,我们把它呃做成幂的加一。
08:04
因为密的加一是我们向右扫描的最右右边最临近中间这个值的,嗯,最右边的那个下,那那那个元素是不是,那Y循环是不是跟这很像啊,同学们怎么写呢?条件改一改就可以了,处这边就应该改成如果它大于了我们。Or点认识?减一说明什么问题?说明temp如果大于二,那减一说明它已经扫描到最右边的,已已经把右边全部扫完了,这个条件还是一样的,如果这个条件满足,说明在向右扫描的过程中,我们发现有一个数不再是find value是不是也该退出?否则应该怎么样呢?加进去,加进去过后这个地方ten步要加一。因为先让臀部向右移,能理解我的意思吧。好相移右移这个过程中做完了以后,我们我们的这一个什么呀。
09:04
就是那个list就可以了。返回,诶,我不叫历史,是result list。是不是好,OK。那看看这些代码有什么问题,他说list in take all OK,那这里呢,我把类型给大家写一下就可以了,怎么写呢?写一个integer。是不是,那这样子做的话,这边诶,他说这边英特尔格尔。不能够转成哦,我明白啊,明白我们这边第这个位置呢,咱们把它这个处理一下,给它保持一致就可以了啊,保持一致就可以了,这样这样子就没问题了,好。给他保持一致,那么现在这边的问题是在于,因为有可能这边返回负一。那这个时候我们就不能够再以负一这种形式返回了,是不是啊,那应该怎么返回呢?各位同学,是不是我们可以返回一个空的list?那么我返回一个空的list呢?我可以通过什么呢?A,我可以通过它的这个size来判断到底有没有纸。
10:08
好,这边就写完,写完这边应该改成二,这边改成二。OK,代码就写完了,对不对,代码就写完了,也就是说现在呢,我们通过这个处理就把所有值全部返回,然后返回的list里面放的是什么呢?这个ineg。是吧,反反的是这个int。好,那现在这个做完以后,那这个咱们就就处理啊,处理完了,这个做完以后,我们可以来测试一下,看看到底OK还是不OK。那现在看我们我们现在这个打印的效果呢。呃,就不能用这个来接收了,这边改成二。我诶我现在改成2A这个不动它啊,不动它我们做一个第二个测试。这个先把它注销一下。对不对,同学们,我们把它注销一下,注销一下过后呢,我们binary。第二种方式的查询方式就是R0还是零,然后这边是r.N怎么样减去一个一查到多少呢,1000。
11:09
对不对,查到1000,我们这边接收到的是一个什么呢?接收的是一个集合。是不是一个集合,好,那我用这个来接收一下就可以了。呃,用什么呢?Result result index list。接收。对不对,接收接收完了,我们可以把这个打印出来给大家看一下。到底是个什么东西?写出来,Result index list。Result index list等于输出我们这个东西。OK。好同学们,我们来运行一把啊,运一把这个地方他报警告是因为我们没有写上这个发型啊,把这个写上就没有错了,来运行一下,现在呢,应该看到有四个,至少有四个对不对。
12:01
好,可以看到4567。是不是567呢,的确是啊,是这是第四个,第五个,第六个第七个我们少,我们减少一个看看对不对。少一个,现在应该找到的是,呃,456是这样子吧,同学们运行值。诶,我们看一下确实是456,如果只有一个呢,怎么办呢,如果只有一个的话,同学们看,那这边就返回的只有。一个。对不对,那如果说一个都没有呢,各位朋友一个都没有呢,我们看这方会有什么问题没有找运行。大家看零一个都没有对吧?那你可以完全通过这个赛制来进行判断,有痣还是没有子?这个呢,代码我们就说到这里啊,比较简单,那这就是我们对这段代码的一个啊一个处理。对这个代码的一个处理,那希望同学们在这个基础上呢,能够理解的更加深入一些啊,这个地方我们要稍微改一下啊,改成这个这个类型。
13:02
历史的这边呢,我们。也用这个来做一下,好吧,把这个改一下,因为我我按接口的形式返回嘛。这样子这边也是接口形式来接收的,这样会好一些,再运行一下。好,没有问题,再加一个1000对不对,再来一个1000运行。好两个都找到了,可以,那我把代码呢,待会整理一下,现在呢,我们花点时间把刚才讲的关于二二分查找和信息查找给大家整理一把,那刚才我们讲的是什么呢?各位我们讲的是。查找算法。略一下思路。操作算法呢,我们新建一个章节对不对,后面还有两组没有讲呢。操作算法。我们给同学们先说的是。查找算法的。一个介绍,就说我们Java里面呢,常用的查找算法有这么四种。
14:01
我们已然给大家讲了两种,对不对?好,这是。列到这儿来。要四种。好,那这四种说完了过后,我们先给同学们讲的是线性查找算法。线性查找算法呢,我们也叫顺序查找。顺序查找,那顺序查找呢,它是注意听啊,它是什么呀,它是不需要你这个数列是有序的,有序无序对它没有影响。对不对,没有影响,好,这是放到这地方来。好,OK,那代码是在哪里呢?我们代码实现给同学们,把代码放到笔记中,就是sequence search。比较简单对不对,线性查找呢,它是比较简单的。放这,那紧接着我们给同学们讲了什么呢?各位,我们给大家讲解了二分查找算法。是样子吧?二分查找算法。
15:00
那么二分查找算法呢?我们先给同学们做了一个思路的分析。是这样子吧,就说二分。呃,我们先是把这个题说出来的,应该是这样子啊,先抛出了一个题。就说也要大家做这个题是什么。是吧,先说这个题。把这个题说完了以后呢,我们就做了一个二分查找的思路分析,二分查找的二分查找。查找算法的思路分析。那思路分析在我们的Excel里面,我们画了一个图。说了一下。在这里。具体来说就是我们总结的这个步骤对不对。总结的这个步骤是这样子的,首先呢,确定数组中间的下标,然后比较,比较完了根据这个结果决定是向右还是向左。对不对,那呃,还有一个特别重要,就是结束递归有两种情况,一种是找到,一种是没有找到,没有找到呢,退出条件是na大于right。
16:07
大于right。好,同学们,这是我们的关于二分查找思路分析的。一个呃,一个说明。来往这边放一下啊。这边为什么。好,放这吧,我把这个缩小一点。是不是小一点。好,这是我们这个图,那么具体来说二分查找的代码呢,也给大家整理到这里,就是二分查找的思路,那么是下面是二分查找的。查找的代码。对不对,二分查找的代码写到这,那同学们注意观察啊,二分查找的代码呢,我们是有这个,呃,增加了一个功能,就是把所有相同的呢,我们都要找出来,是不是把这个列出来,还增加了一个说明啊说明。说明增加了增加了找到,找到所有所有的满足条件的元素下标。
17:08
的元素。对不对,元素下标这个功能。具体来说就是这个要求。是吧,那代码呢,我就直接给同学们整体的放过来。一个bary,一个是B2。给大家放入到表格中。来一个吧。好,同学们,这就是我们二分查找的一个,呃,分析和代码的实现,那下面呢,我们。给大家准备说差值查找算法,那差值查找算法呢,我们放在下一个视频为大家进行讲解,这一节课先给同学们讲到这里。
我来说两句