00:00
各位同学,我们来看一下数组的查找,对数组的查找这个内容。那么数组的查找呢?在C里面我们常用的有两种,说白了查找就是说我们看看在一个数组里边有没有一个我想找的数,那么有两种,一个呢叫顺序查找,一个呢叫二分查找,我们先看顺序查找,顺序查找呢,它是一个比较简单的案例,说我这里有一个数组,判断这个数列里面是否包含该数。那么如果找到了过后呢,咱们返回下标值,如果没有找到呢,返回没有这个数,就这样子好,我们顺序查找呢,这个思路很简单哈,我们一边写一边分析就可以来,咱们写一段写一个代码。写成代码来完成它的一个查找,好吧。走一个,那现在我先把这个。注销。好把它先注销,因为前面我们这块呢,已经把它呃排序好了,我们先来写一段代码,叫做find查总。
01:07
Search吧。Search。啊,Sequence就是顺序查找,叫sequence,我们这样写一个search sequence。那现在呢,我们把这个后缀改一改。好,现在呢,我们写一个叫include。STDIO。然后VO的主函数。我先有一个数组往这放一下。我的思路呢,先给各位朋友分析一下我的思路。分析思路,顺序查找特别简单,就一个一个的比比较,找到了就返回就行了。就是按照。按照这一个数组。干什么呢,进行。进行便利,进行便利一个。一个。
02:00
一个一个的比较,如果相等,如果相等,则找到。就这简单,好,那现在老师就来开始写一个,我我直接就写,我直接就写方法了啊同学们,咱们直接写一个方法就可以了。那现在呢,因为它返回一个int嘛,我们就这样返回一个索引,那就小Sequ search。12SH,首先呢,你给我传一个数组过来,好,我把数组先拿到,然后呢,你告诉我这个数组的大小是不是啊,然后呢,你告诉我你要查找的只是哪一个value就可以了。那我现在怎么写呢?大家看我可以这样去写。啊,这个嘛,写错了。对,我我可以这么去写了,按顺序来嘛,那就便利。For循环。我先写个it I。那么不循环了。
03:00
For开始循环了,刚才老师说了啊,I等于零,I小于我们的I加加,没问题吧,同学们I加加,那么我就进行一个比较,如果说我发现当前这个元素的值就等于你要找的值,说明成功。是不是找到了?好找到呢,我把这一个当前索引返回。这个不是文员说了吗?找到找到了就提示找到病。并给他返回一个下标志,找不到就提示没有,好,我这边就返回一个当前值,如果整个这个for循环结束了,还没有return,就是这个函数还没有返回。那我们不是讲过吗?会提前返回,如果他在这个过程中一次都没进来,那他只能是退出这个for循环,如果退出for循环,在这我们就return一个什么呢?如果啊,如果在for for循环中,循环中没有执行到return说明什么?
04:06
说明没有找到。那这时呢,我们就返回一个负一。因为我们下边不可能为负一,所以说我们通过看你是不是负一,就知道你有没有找到蛋白去,写完了来,同学们,我们我们玩一把,非常简单哈,来,我们首先整一个数组。这个数字呢,先放这儿。对,然后呢,诶这边是不是有一个空格的问题,那就好。这样就可以了。这边。重新梳一下。这个应该也是个中文的逗号,好像就没问题了。我现在能接收一下这个index,等于调用我们这个sequence sir变变小了啊。放大一点,调用sequence search,我把数组扔进去,当然它的大小是多少呢?就这个数组大小是不是咱们可以这样算一下的,把它数组的大小计算出来是size of。
05:07
除以size of in没问题吧,同学们,那现在呢,把这个扔进去。对,然后呢,我们要找哪个数呢?比如说我们要找的是101。101,好,现在我们判断一下,如果index不等于负一,说明什么?如果不等于负一,说明我们找到了。是不是找到了呀,因为前面我们不是讲过吗,负一的时候呢,就代表没有找到,所以说这边我们写出就说没有找到。如果没有找到呢?我提示一句话,来,朋友们,If,我走,一句话就说没有找到。没有,诶没有,诶等于负一下是啊说这个应该是找到哈。不等于负一就找到了吗?找到下标,下标为,注意不等于负极是是找到了。
06:01
因为我们讲过。等于负一才是没有找到哈,刚才我们说说反了,找到了下边为多少呢?好给它输出一下,就是这个index。是吧,A。要说明他什么呀,等于负一,等于负一就是没有找到。Pretty。没有找到。好同学们,我们运行一下,大家看现在呢,我是101,它如它应该是找到才对,那下边应该是几呢?01234应该是四,我们运行一下。我们给各位同学运行一下,看看结果是否是一个四,如果是四,说明我们这个代码呢是OK的。诶,这个一闪而过,不好意思,Get。一个串。对不对,我们运行一把。Get。Get下过呢,我们看一下这个结果哈。盖下呢,现在是是正确找到了。那现在呢,我找一个没有找到,我放一个没有的数负101,各位在这个数组里面有没有负的101呢?并没有,并没有的话呢,我们运行。
07:09
对,我们运行,那么我们运行我们发现呢,的确它会返回一个没有找到这个提示。正确好,所以说我们这个顺序查找呢,咱就讲完了,紧接着呢,我们再来讲一个二分查找,二分查找,那么二分查找呢,它是一个什么概念呢?首先看这里。对,他首先是对一个有序数组进行这么一个查找,换言之就是说二分查找有个前提。什么前提呢?是一个有序有序的数组,所以说我先说明一下。就是二分查找。二分查找的前提。前提是什么呢?是该数组是一个有序数组。
08:00
因为他是一个从小到大的,或者是从大到小的。那么他的思想是什么呢?他的思想呢,我一边写一边给大家做分析,好不好,还像刚才这样,我们直接上代码了。那现在老师给他写一个二分查找的一个小案例,跟着老师思路。来走一个,那现在呢,我们写另外一个叫二分查找binary。Bary是二分的意思,二二二进制的意思,Binary search。没问题吧,BB设CH。然,然后我们把这个CPP改成一个C。那现在呢,我们走一下,Include std IO。好的,这是我们引入的头文件void主函数。主函数。那现在我先把这个数组拿过来,我们先说一下思路。大家注意听,看看我的思路是什么样子的好不好?一定要认真听哈。我们来做一下这个思路分析。
09:02
然后再走代码第一步。那么待会儿我怎么去完成呢?我们先找到,因为它是个有序的数组,我们先找到,中间这个数先找到。先找到朱婷,找到数组中间这个数。然后呢,和和这个数,比如说我们,比如说我们要找的数这个。比如我们要查找的数是,叫做find value。就是这个中间这个数呢,假设我们叫me的value。找到这个中间这个数以后呢,和这个范的value比较。对,那么比较呢,就会有这么几个情况,第一种就是如果,如果什么呢?如果me value。它大于范的value说明什么?说明什么?说明你要查找的,你要查找的这个数呢,是比中间这个数小的,因此你应该向它的哪块找呢?假设我们中间这个数是89。
10:13
而我们要找的数呢,是八,8:89要小,那么就说明我们应该在它的左边去查找,是不是这个道理,说明注意听,说明应该在。说明应该注意听,应该在哪里呢,密的。Mid value的左边,左边查找。是不是好,那还有一种情况呢,如果me的value。小于find value,说明应该在me value的右边查找,为什么呢?因为你是从小到大嘛,而我这个find value比你中间这个数大,那么我只能在它的右面去找,看看有没有还有一种可能性什么呢?是。哎,还有一种可能性就是什么呢?如果相等。
11:04
就是find me的value等于我们才find,说明找到了。是不是这个意思啊,说明找到好说明找到,那么我们这个基本思想就写完了。基本事项就行了,那各位同学我们来给大家写一下这个代码,二分查找,当然我说了啊,这里面肯定还有一个问题,这里还有一个问题,我们一会儿单独说。待会儿呢,我会告诉大家,我们上面这个前四部的分析呢,还有一个漏洞,待会儿再说,这个漏洞是什么,我们先把正规的先做完好,现在呢,我仍然是返回一个int啊。到了bary。写上同样道理,你把数组传给我。然后呢,你把数组的这个,因为你现在问题是这样的,同学们。他要找到中间这个数,那你需要把这个,把这个查找的时候的最早最左边的坐标和最右边的坐标给我,所以说我先要接收一个left。
12:10
Index,还有一个right index,对,这两边我是必须要要的,然后还有个什么呢?要查找的值,Find。Value写完了,那老师开始来写好,我们首先找到中间这个数。中间这个数好不好找呀,其实非常好找。可以这么去找,我先找到中间这个下标。Mid index index,当用left inex加上right inex除以二。各位,这个是不是就是中间数的下标啊?就是你左边的,比如说你左边最先前是零,最右边的下边012345就是五,那么零加五除以二是不是2.5 2.5呢?去掉这个小数位就是二,也就是说现在中间这个数是不是就是下标为二,这个数是哪一个呢?012,那就是这个数。
13:15
就中间这个数是,中间这个数是十。这个没问题啊,没没问题,那如那现在现在找到这个中间数呢,就按照刚才老师的这个思路写代码就行了,来进行比较吧。来走一个,如果me value,注意听哈啊,中间这个数,中间这个值还没找到。Me value。等于多少呢?显然等于R。这个mid index看到没有好中间的值,那现在开始比较,如果中间这个值它大于三的value。各位,它大于find,说明我们应该在左边去找,那怎么去体现左边去找呢?我用一个递归。
14:03
你要往左边去找吧,那就是把数组继续往下传,左边找是不是相当于找这半拉呀。那它的左边的坐标仍然不需要变化,而右边的下边呢,是原先中间的这个下标怎么样?减掉一个一,这个大家能理解吗?当然这个要查找的值继续往下传,这句话要好好的理解一下同学们。这句话是大家看啊,这像左边去找数组还是传进去,这是左边的索引,这是中间索引点一,因为你你想吗?同学们,你原先比如说找的是十。那你要在左边去找,肯定这边零不变,然后在中间这个索引减去一个一不就是八了吗?就相当于在这个数组里面找明白了吧,所以说这边要减一啊,这个道理很浅很浅很浅显,L if来再找一个,如果我们这个中间的值呢?它小于这个find value说明什么呀?说明我们应该向哪边去找呢?老规矩拿过来。
15:10
说明我们要向右边去查找。明白,那右边去查找,不用多说,把句话拿过来怎么改呢?右边先去查找,其实说白了就是找这一半了。那找杯这版呢,你的右边的原先右边的索引不需要变化,而左边的索引呢,是中间这个索引加一,因此它就变成这样子了。左边这个缩音变成mid index加一,而右边这个,所以呢仍然是传过来的。Index单写完,最后还有一种情况就找到了,那如果找到的话呢,咱们非常高兴直接return哪一个呢?当前这个坐标其实就是me index能理解吗?同学们。诶,返回。返回该数。
16:01
甘肃。的下标代码就写完了,那还有一种可能性,同学们看,如果。这这个地方我们先写完了,我们我们现在用一下好不好,先用一下看看对还是不对。我先把宿主拿过来。刁超老师,思路喽,这稍稍有一点小麻烦,有一点需要动脑筋的地方了。那么现在呢?我把数组的N,数组的这个最大小算出来。NN等于多少呢?是不是应该等于size of?Size。Of什么呢?除以size of。赛走什么呢,Ink?是这样子吧。好,假如我们要查找的值,我们也定下来哈,我们现在开始调用了,首先我用一个index来接收。那我调用了谁呢,调用。
17:00
Binary search,让我传一个数组进去。左边是零,最先前右边是我们这个数组大小减一,为什么要减一?我不说了,因为你你你你的大小为五,其实你的最大的索引最右边那个索引其实是减一。我们要查找数。假设是一。OK,找到了,那现在呢,我们来看看是不是找到了哈。Index等于来个百分号D。那么我收,我把这个出出来,如果不出问题。如果不出问题,这边应该返回几呢?返回一个。返回一个零,因为一的下标就是零,我们运行一下好先把这边呢注销。注销过后,朋友们,我们运行一把看效果。看效果好,跟着老师思路。那么运行起来过后呢,我们看到index的确返回零正确的,我们再找一个别的吧,比如我找一个89。
18:02
89的话,不出问题的话是0123应该返回三。我们运行之,我们看看是不是三。我们看看是不是三,我们发现呢,它返回的就是一个三。没有问题,但是有一个漏洞,我们没有考虑,没有找到的情况,大家看你在整个过程中,你从来没有考虑没有找到情况,那眼眼外之意就是说如果我这有个负的89,负89在这里面没有,没有你这个地方调用的时候呢,没有考虑。终止递归。所以说这就会出现一个很可怕的现象,就会看什么呢?站一出我们看这个程序,就会很麻烦的看运行。这个时候就会变成什么样子呢,你看。同学们看这里啊。你看。没有返回,没有返回,最后这个程序就异常的终止。异常,所以说我们这边有个漏洞,就是什么呢,没有考虑。
19:02
没有考虑找不到的情况。那怎么解决这个问题呢?我问大家一个问题,就是我们这一段代码在什么情况下就表示我们找不到了?能理解吗?什么情况下表示我们这个二分查找失败,或者说找不到了。我跟大家说一下是不是这样子的,同学们,我们在整个过程中,左边右边是从最先先从这个位置和这个位置开始的。那么随着你的这个二分是不是左边的这个left的。Lap的这个索引它是向右边移动,而右边这个索引呢,向左边移动,是不是在这样子移动扫描。那么如果我们左边这个下标,左边这个下标它在某个时刻大于了这个right,说明我们已经扫描完毕,还是没有找到。
20:00
也就是说,如果left索引大于了右边索引,就说明找不到了,因此这个条件我们就分析出来了,那同学们看,我们在这应该加一句话。如果left index大于了right index,说明整个数组都。都处理都便利过了,或者都都都比较过了,比较过但是但是没有找到。那这个时候就应该退出,那就写这样写,如果left index大于right index,在这个条件满足的情况下呢,直接不用犹豫,返回一个负一就可以了。这个条件非常的重要,一定要分析出来。好的,那既然如此,那同学们,下面老师是不是可以这样玩了?怎么有呢?If,如果index。不等于负一。那么我们就提示一句话,找到了。
21:00
是不是index,呃,找就找到啊,就直接写个啊找到,那么如果它等于零了呢,各位我提示另外一句话说没有找到。没有找到。代码就行了。啊,所以说我们再来玩一把,现在呢,我们写个负89,看看能否能否提示没有找到,而且程序呢,也不会异常的终止,看情况。我们运行,诶这个代码看看哪里有问题哈。哪里有问题?哪里有问题,我看。呃,他说。这个为什么会加上,哦对我们这句话啊,同学们不能写在最前面,我们需要把它写在这两个定义的后边,这样就可以了,写到这一样的一样的,因为在这个地方呢,Left right没有发生变化,好这样就可以了,再来跑一个。
22:00
运行,那运行过后呢,现在应该返回一个没有找到的提示就正确了。我们发现没有找到正确的。对不对,那现在我们再回再找一个能找到的哈,负80又找不到,现在找一个1000。看看一千一千能否找到。把这个符号改掉,我们看1000是否能找到运行。那运行运行起来过后呢,我们看到它应该返回一个01234,应该返回一个四,正确找到了,好再写一个负负1000找不到。试一下,因为我们写完代码过后,如果不测试呢,你不敢保证你的代码就是正确的,所以要多测几遍。B找到正确,好各位同学,那到此呢,我们就把查找给各位同学讲完了,我们把代码给他梳理一下。查找内容。好,梳理到这里,好吧,也并不难。查找。那操作呢,首先我们做了一个简单的介绍。我们做了案例的演示。
23:00
好,我们讲了第一个案例和第二个案例,对不对,那我把代码给大家放过来好吧。这是我们的第一个案例。第一个案例,我重新给他标一下号,这个看起来不舒服。好,这边我也给他重新标一个号好吧。这边一标呢,就会自动排序变成二,我把代码给他拿过来就行了,代码呢,第一段代码是顺序查找。顺序查找呢,我把代码和它的分析。整个放入一个表格。紧接着呢,二分查找是不是我们也给大家讲了呀,在这里。包括这边的分析流程咱都有。可以了,那最后我做一个要求,同学们呢,在听完这个查找过后,我要求同学们二分查找,大家能够默写下来。要能够默写,就说你不看老师的提示,你也能够完整的把老师的这一段代码。写出来哪一个呢,核心单位就这块儿。要把它写出来,这是一个最基本的要求,同学们一定要在课后去练习,否则的话,这个学习效果是非常差的,就老师怎么讲你都学不好,你一定要去自己写一遍,就你你先理清楚思路了,然后呢,你不看老师的代码自己写一遍。
24:14
这是一个要求,同学们好不好?各位关于查找的内容呢,我们就给大家讲解到这里。
我来说两句