00:00
同学们,我们用代码来把这一个插值查找算法给大家实现一把,那打开我们的这个eclipse,我们开始写这个插值查找,OK,写个类,那这个类的名字呢,我们就叫insert,好吧,Insert value。什么呢?B或者search。1CH就是差值查找算法,OK,勾上主方法。ARCS,嗯,那么还是老规矩,首先呢,我把这个数组给大家写上,刚才我们在做测试的时候,是不是用的是这个数组啊?对吧,那这个数组呢,咱们这样生成吧,好不好,那我们写个数组R。等于什么呢?诶咱们六是不是先溜一个这个空间出来,溜一个int,然后这个大小呢,咱们定义为100。这个没有问题吧,我for循环100I等于1I小于等于100没问题吧,I加加各位,那现在呢,我们每遍历一次就把这个值给到他啊对了,那这样子,因为下标呢,咱们还要保持一致,所以说这样子写的I。
01:18
对不对,负值应该怎么负呢?I加一就可以了,这样就是一到100,这个没问题吧,同学们,这是一到100的一个数组,我们可以先呃打印出来看一下,待会呢,我做一个对比,对不对,Two。使君。输出来。这是目前这个数组呢,同学们可以看到是一到100。对不对,一到100的。一个一个数组,好的,有了这个数组以后呢,我们现在直接就开始写我们这个差值操作算法,那么现在呢,编写编写这个差值。插值查找。
02:00
对不对,查找算法好,那现在呢,我们先写一个方法叫public static void。啊,就不是贸易的,我们仍然返回一个int啊,这样我们在这查找查查找的时候呢,我们就假定返回一个索引就可以了,如果同学们要去把所有的都找到呢,就在原先那个基础上改进,我现在写个int。好,那现在呢,就写insert什么呀,Value。1CH,那同样你给我传什么呢?首先你要把数组传给我,这个没问题吧,同学们,那int left,左左边的索引,右边的索引,然后呢,还有一个你要。查找的是find value。我把它全屏一把。好,嗯,那这里面的这个注释,关于这些参数的含义呢,我这里。简单的说一下。这边是传入的数组。
03:01
对不对,这是左边的索引。左边。左边的索引或者下标,这是右边的索引,那这个是我们要查找的值,没问题吧,那现在开始写代码。那写代码的时候呢,同学们,我们可以根据前面二分的思路来写,都是这样的,首先呢,我们有一个判断条件,就是什么情况下我们就要退出呢?就是当我们的ne。诶,我们left大于什么呀,大于right的时候,我们就要退出,是不是以前是有这样一个条件,直接返回一个负一。这个返回值呢,是这样子的啊,如果找到,如果找到就返回对应的下标对吧,如果没有找到呢,如果没有找到,返回一个负一就可以了。那假设,那么我们再加两个条件,为什么要再加两个条件呢?呃,实际上是这样子的,因为我们本身这个数已经是个有序的了,那如果我们查找的数find的value它小于最小的,那肯定就找不到,或者说find的value大于最大的,是不是也找不到啊,是不是我们可以提前的终止,提高我们的效率,那我这样写了啊,Find value。
04:19
如果它小于我们零,说明什么问题?说明。你,你比最小的还小,那肯定就没有了,是这样子吧,我们可以提前终止,那么同时呢,Find value如果大于。啊,如果它如果大于了我们最大的这个数,最大的数是不是2.n减去一个一。如果在这两种情况下,我们就可以提前退出。没有必要再往前面走了,是不是?因为你你这个可以判断出来吗?也就是说我们这个差值查找算法呢,也要也需要我们这个数组是有序的,明白这意思吧,我这里做点说明好不好,说明就是差值。
05:01
差值查找算法也要求,也要求什么呢?要求数组是有序的。没有问题吧,同学们,那接着我们继续往下走。继续往下走,那现在呢,我们要求出求出什么密的这个公式我们在刚刚先前已经有了,老师就不啰嗦,直接拿过来用。就是我们刚刚写的这个公式,是不是拿来用就可以了。对吧,同学们好,往这儿靠一杯。就可以了,那这一般可能是符号的问题,改一下。这个符号呢,因为呃,这个它的它的符号和那边不一样哈,把这边改一下,改成减号。好,这个就没有问题了,找到了,那找到以后下面我们是不是还是一样的规则,把中间这个值也就找到了,就是me的什么呢?Value我们是不是也找到了mid的value等于什么呀?是不是等于R上面这个mid呀。
06:00
是不是这样子的,跟我们前面一样吧。找到中间这个值,现在我们就开始比较,如果说我们查找的中,我们这样说啊,如果我们查找这个值。我们查这个值,它大于。这个中医中现在你定位的,定位到的这个值。对吧,你定位到这个值,就是说我们查找的值比你这个值还要大,说明什么呢?说明说明应该向哪里。向哪个方向递归查找,比如说我我要查找比你现在你定位的就标杆这个值要大。要大。如果我比你大,那说明呢,我应该向右边进行查找,右边递归。右边地柜。啊,说说清楚啊,现在我们数组首先要确定是从小到大,如果你是从从大到小呢,刚好要反过来试一试吧,那向右递归查找应该怎么写呢?一样的道理,Return,我们insert value。
07:08
竖左传进去,既然你是向右边查找,显然是应该用密。是不是幂的应应该怎么样加一个一。加一个E,右边这个不动,Find value不动没问题吧?好,紧接着我们继续写,如果else if,如果我们查到的这个值它小于me的value。那说明什么呢?说明我们应该向左边递归查找。对,说明向左递归查找,这个呢也很好写return。他们return一个什么呢?同学们,Insert value search是不是?那这样速度传进去,既然是向左边,那左边不动,而右边这个下标就变成米减一。是这样子吧,同学们好,非常的简单啊,非常简单,我把这个格式化一下。
08:04
我把这个格式化一下。好的,那最后呢,还有一种可能性就是找到了。那L就是它们相等,如果相等我们就不啰嗦,直接把这个返回就可以了。好同学们,关于我们这一个差值查找算法,我们就写完了,其实大家有没有发现,主要是这里变化了。上面呢,我们加了一个判断,这个判断必须要啊,如果这个判断没有的话呢,有可能造成这个密的越界,因此这两句话不是可有可无,而是必须有,我说明一下。注意。注意。注意什么呢?就是这一句话。这个条件和。和这个条件,它不但能够起到这个优化的作用,而且必须要是必须需要的,需要必须需要。必须需要,否则。
09:00
否则,我们得到的。得,得到的这个密,这个值可能越界。可能越界。大家可以去呃,想一想,假如我们要查的值特别特别大。你想啊,假设我们要查这个值,这个假设我们查了一个要查到值,我故意写了一个巨庞大的数,那你想你这个公式na加上这个值乘以一个巨大的一个,一个值除以它将来也这个幂可能很大,那你上去过后,你这样一取嘛,就出错了。明白我的意思吧,所以说你这个地方呢,不能这样写,因为你你整个这个find只是参与到去求这个密的索引的。因此这两个条件必须得有,否则要越界啊,好,这样写完了,过后呢,同学们,我们来玩一把,看看我们能不能找到,先来看能不能找到同学们。好的,那现在呢,我们,嗯,我们先把这个先注销,我们来玩一把insert value,好把数字传进去,Na的肯定是零,Right应该是什么呢?RN减一没问题吧,我要查的数假设是100。
10:14
假设是100,那假设是100,现在呢?我们得到了一个索引。得到一个索引,那现在呢,我可以把这个索引打出来给同学们看一下。那同学们看到。Inex等于多少呢?等于这个index。是不是同学们,我们来运行一下,看能不能找到,现在应该是找到下标为多少,应该是99。好,我们可以看到的确是99,没有任何问题,没有任何问题,那现在呢,假如我们呃,找的是一,我们看看有没有找到,我把这个全屏一下。好,全屏一下,大家看一反馈的声音也是对的,那现在我们关心的是什么呢?我们关心的是你到底找了几次,那现在这样子,我把这个这本打印一句话。
11:06
我们看看这个方法被调用了多少次才找到我们的。要找到这个值好这里呢,我写一个什么呢。啊,查找次数查找,诶就要查找查找次数啊,就这样打这一句话吧。我们来看看当我找一的时候,我一共调用了几次呢?运行大家可以看到,诶,只调了一次就找到了。那同样道理,我把这个改成100,我们来运行,大家有没有发现。查找次数,一死就找到了。那你换成别的值呢,也是可以的,比如说78,我帮你看查找次数呢,一次就找到了,快不快,很快说老师,那你用二分查找来比较一下呗,可以,我把二分查找也拿过来,这是我们最先写的,这个传统的二分查找是不是我们也拿过来看看两者有没有一定的区别。
12:03
好,这是我们最先前写的这个二分查找。那么二分查找我们也也在这里面呢,也来打一句话,我写一个叫做二分查找被调用。我们看看这句话输出了几次好不好,同样我把这个呢改了。没问题吧,我现在把它改成什么呢?我把改成传统的二分查找。好,同样它也是零,这边是什么呢?r.N这边值假设我们是100。各位,我同样用一个int来接收。各位同学请看,我现在用二分查找,看看它调用了几次运行值,我们可以看到二分查找调用了重值。当然他还是找到了下边为99,的确,因为100的确是在这个位置,但是你看调用一次两次,三次,四次,五次六次对不对,那如果说我们要查找这个一,同学们可以看到它调用的次数呢,也是六次。
13:04
不划算。多了有多了五次是不是,那有些同学说,老师那我我们用原先那个数组可不可以达到效果呢?大家看我们原先最早的时候是不是这个不连续的。我们看看对于对于这种数组能不能也起到一定的优化效果来走一个。好,我把上面这个数组先。注销各位现在呢,我们用我们用这一个。哎。我们用哪一个呢?我们就用这个这个传统的二分查找来找这个一,我们看看找到了没有啊,看关键是看几次来运行一下,我们发现呢,诶。你的确找到了,但是调用了三次。是不是调用三次对吧,我现在呢,换成我们的差值查找。差值查找好,我在这儿把这个再写啊,差值查找。差值查找次数,我们现在调的是插值查找来找我们的这一个。
14:06
呃,原先的这个数组的值,比如说现在我们也找哪个呢。也找一,我们看看这次它能几次啊,运行一下我们发现呢。一次搞定,你看在这个时候他也能够在一定程度上提高我们的效率,看校标为零嘛,校标为零是不是。就找到这个,那我把它换成1234。比如说现在我要查的是最大这个数,1234。好,我们来运行值插值查找呢,这个时候也是一次导力,看到没有,很神奇,为什么他会做到这样一个效果呢?就是因为他在求我们这一个。中间就是所谓的这个标杆,或者中间这个索引的时候呢,它其实本身这个值也参与到这个里面的一个计算,所以说我们把这个称之为什么呢,叫做自适应。字适应的一种写法。
15:01
OK,好,这就是我们的这一个。插值查找的一个代码的实现,而且呢,我们也看到的确在一定程度上可以减少我们查找的次数,从而提高效率,那最后我要做一点总结,各位朋友,那么插值查找的注意事项是在什么情况下用比较好呢?就是对于数据量比较大,关键字分布比较均匀的查找表来说,采用插值查查找速度较快,这里所说的关键字就是指的值。就是说我们这一个。呃,数组的元素的值第二点呢,关键字分布不均匀的情况下呢,该方法不一定比折半查找要好,不一定好,你看刚才这个实际上这个就不是很连续,你看一八十八十九,一下就1000,这边是1234。对吧,他也不是很连续,但是呢,你看到他还是优化了,他这里所说的呃,不分波不均匀是指指的跳跃性很大的。
16:00
跳跃性很大的情况下,这个插值查找呢,就不一定比折半查找好还好。好,关于这个差值查找,我们说到这儿,那下面呢,我把刚才讲的内容给各位朋友板述一下,那刚才我们讲到什么了呢?各位朋友我们手我们在查,呃,讲的这个差值查找算法。差值查找算法,首先呢,我对差值查找算法的原理给各位同学做了一个介绍,就它的工作原理是怎么回事,是不是有四点呢,把它列出来。这儿有四点。诶,这这有没有这么多啊,插值查找这个不要了。好的,这这个地方是啊,我看看啊,插值插找从这里。开始,呃,那这个就。江浙办啊,这个地方。好。呃,这个这个不要啊,这个不要好这就可以了,那查找他查找算法的工作原理,我们把这个相应的图也给同学们拿过来就可以,好不好,这是这张图。
17:07
这个图呢,是一个公式的,怎么样推,推演的一个过程,大家呢,要有一个印象就可以。啊是怎么来的,至少知道,然后呢,我在下面呢,把这个公式说做了一定的调整,怎么调整呢,把这个hilo放在前面去了,对不对,然后呢,我们为了加深大家认识呢,我们举例说明了一下差值,差值查找算法的它的一个过程是什么样子的,是不是在这讲的呀。我把这个呢也给各位同学拿到笔记里面来。这是用了一个实际的案例来说明查值、插值、查找算法的过程。从而加深对插值查找的一个理解。好,那这个写完了过后呢,是不是我们就用代码给大家走了一遍是吧,这是这是案例,那么下面呢,我们就用代码给大家写了一个。呃,差值查找算法的代码。
18:02
走一个。那具体来说代码呢?我给大家拿到笔记里面代码的实现。代码实现。好的。从这挪一下啊,代码实现呢,我。把这边写的代码给各位同学放到笔记里面来。插入一个小表格对不对,放进去,那这说完了以后,是不是我们还说了一下差值查找算法的一个注意事项,就一般来讲呢,在数据量比较大,而关键词比较分布比较均匀的情况下,我们这个叉子查找呢,它。要他查找速度快,是因为他定很快就定位到你要找的这个值,但是在不均匀的情况下呢,不一定比折板好,这点大家要注意,就是说你在面试的时候呢,要把这个注意事项给别人说出来。好,我写到这里啊。写到这里,这是叉子查找的注意事项两点,诶,这个地方我要往下面,哪一点好,同学们。说到这儿吧。
19:01
好,两点捋捋。好,同学们,那关于插值查找算法呢,我们就给大家讲解到这里。大家。理解一下。
我来说两句