00:00
同学们,我们接着来看下面一种差值查找,呃,算法。那么二分查找算法呢,它有它其实速度已经很快了,对不对,因为它是折半嘛,效率其实已经很高,但是我们可以再对它进行适当的这个优化。那么我们来看一个这样的一个情况,同学们打开我们这一个二分查找的代码,如果说。如果说我有这么一个数组,大家看会出现一个怎样的情况?比如说我的数组是长成这个样子的,怎样做的呢?12345。六。七。八。90好,我再写几个啊,十一十二。13、14、15。16、17。18。19、20。好,同学们可以看到目前我这个数组呢,它是一个连续分布的。
01:05
同学们,假如我现在要去用二分查找。查找哪个数呢?比如说我要查找一。我要查找一,那么我们先来运行一把。来看看他能不能找到一,显然它是可以找到一的,但是同学们考虑它虽然找到了一,大家知道按照我们这个二分查找,它一共查找了多少次吗?我们来看一下。好,为了能够看到这个效果呢,我简单一点,好,同学们,我在这个b search里面打印一句话,比如说。我们这写一个什么呢,就叫哈吧。那么我们来执行这段代码,我们来看看他一共调用多少次。同学们可以看到,诶这句话没有输出,诶写错了,这个应该写在哪里呢?应该写在我们的下边,是这样子吧,因为我调用的是binary search2,我们再来运行一把。
02:03
好,同学们可以看到他一共调用了一次,两次,三次,四次,找到了我们这一个。一。那这样实际上是有点不划算的,为什么呢?大家想。我们现在找到中间这个字。然后进行二分,我们能不能。通过一个办办法,能够快速的用一种自适应的方案,能够快速的定位到我们要查找的这一个一呢,也就是说我们能不能够对我们这一个密的这个值进行一个改进,让它能够快速的定位我们要查找的这个值。明白我的意思吧,其实是可以的。这个呢,就可以用我们的差值算法来搞定,那现在呢,我们来介绍一下差值查找算法的工作原理。那么差值插到算法的,它的工作原理呢?类似于二分查找。
03:01
不同的是插值查找,每次自适应密的处开始查找,也就是说他在找中间这个索引位置的时候呢,它是采取了另外一个方案,自适应的方案。那它的公式就变成这样子了,大家看我们折半查找,也就是我们前面讲的二分查找,它的密的这个索引的求值公式是这样子的,是不是用no加hi除以二,注意这个no就类似于我们这个代码里面的ne hi呢,类似于我们代码里面的right,也就是说这样子啊,大家看我写到这。也就是说他这个no左边索引left。Hi表示我们右边,所以right这个没有问题吧,同学们好,我把这个往这边移,打开一点就可以了。这个应该大家能能够理解老师在说什么。对不对,那也就是说这个公式是这样子的,那这个公式我们可以看到,如果我们写成这个形式,大家有没有发现其实是no加1/2HI减nor,是不是这样子折办的呀。
04:08
那现在呢?如果我们用差值查找算法,我们可以怎么做呢?我们可以这样写。Need等于no,这个不动,后面这个high。简陋啊,我们也不去动它。但是呢,这个1/2这个系数或者这个因子数呢,我们做调整,怎么调整呢?让这个K减掉。No。然后除以a hi减去a nor,注意这个K代表的就是我们要查找的值,我写一下啊。我写一下,就是同学们现在看到这个K。同学们看到这个公式里面写这个K代表的就是我们要查找的那个值,等于什么呢?就是前面我们讲的。讲的哪个呢?Find value。Find。Value。
05:00
那这样改了过后有什么好处呢?同学们,如果这样改的话,我们这个公式就可以写成这样子的了。就是我我还是按照我们原先这个啊,密就等于什么呢?密就等于no加hi减no,注意我把这个题提到前面来了。我把这个。捡起来这个值提到前面来,再乘以后面这个值。后面这个是不是K减六,这个肯定要括起来除以。下面这一个,呃,差值是不是好,那也就是说我们再去找这个中间索引的时候呢,我们的公司就变成这个了,变成这样子,那对应我们的代码变成什么呢?来我写一下对应前面的代码。我们这个公式就变成这样子了,给给给大家写一下。对应前面的代码呢?这一个公式就变成了这个德行什么呢?Int need等于no,是不是left?加上我们high还是不right?减去什么呢?Left?
06:05
乘以什么呢?各位朋友,乘以我们的要查找的这个值叫范,诶各位同学诶。这个地方find value减去我们nor什么呀?然后再除以我们的这个RA,什么呢?Right,再减去我们的left。也就是说我们再去求中间的这个索引的时候呢,我们就按这个算法来做。那有些同学就说,老师,那这个有什么好处呢?来给同学们举个例,说明我们这个差值查找算法的一个优秀性,比如说现在呢,我有一个一到100的这个数组,如果我们用这个幂的这个公式来找,我们看看经过几次就能定位这个值。好不好,我们来看一下吧,待会儿呢,我们来演示好,打开我们的这一个Excel。
07:03
我们给大家呃,做一个。做一个解释,大家就明白这个含义了,待会呢,我们代码实现就OK。好,现在我插入。一个这样的啊,我们说一下差值。差值查找,查找算法的一个举例说明。举例说明,比如说现在呢,我有一个数组。我把这个呢调成我们的这个颜色,好吧,说我现在有一个数组是这样子的,数组是什么呢?是。All right。怎么样写的呢,大家看啊,呃,我就简写啊,就一二三点点点点点点点到哪里呢?到100没问题吧。Man。那么如果我们按照传统的传统的这个二分查找的话呢,它是left加right。
08:00
那这样子它第一次定位的是哪一个数啊,是不是我们下标,如果是零加99除以二,那你是可以算一下,也就是说我们中间这个下标是。99除以一个二,那等于多少呢?等于49,那也说我们定位到下标为49这个数开始比较,也就是其实就是50。那么50不是不行的话,是不是你要折半,那肯定要比较好多次嘛。你才能定位到这个一啊,定位到你要查找的这个值是不是好,现在假定我们要查找的值,比如现在假如,假如我们需要查找的值。哦,我们查找的这个值是多少呢?值是一。那么看看啊,呃,我们使用这个二分查找,就是就是二分查找,二分查找的话,我们。画。我们需要多次多次递归,递归才能找到,才能。
09:04
对不对,才才能找到什么呢,找到这个一。是不是这个我就不去比了,因为第一次你折半嘛,折半你到呃下边为49 49不是,然后49对应的这个值不对,然后你再向左递归,是不是要多次啊,那现在如果我们使用注意听,如果我们使用的是差值。差值这个查找算法的话呢,我们来看它会第一次得到的密是多少,来把公式给各位朋友拿过来,公式是不是这样子的。是不是老师写的这个样子的,来我们看一看。那么如果按照二分查找,这个int就应该等,呃,这个me就应该等于什么呢?Left left第四,四,零加上我们的right right是九,99对不对?下边再减去一个零对不对?各位朋友乘以什么呢?诶,OK,乘以我们要查的这个一。是不是一减去NENE是几零一是不是?
10:04
是是不是一嘛,因为你你查到的是一,但是下标,你第一次进的LA的下标为,呃,LA的是零嘛,那就是一减一,一减一,再去除以后面的这个值,后面是什么呀?而right right最大这边是不是100啊,再减去left是不是一,好我们看等于多少所等于零加上一个。99乘以。什么呢?OK,乘以的就是零,然后再除以。对不对,除以99,显然这个值就应该等于多少,你99乘以零不就变成零了吗?那有时候整个这个是零,包括同学你们有没有发现很神奇,我们这个密的。就是您。诶,你们有没有发现一下就定位了。是不是我经过一次比较发现,诶,就是一。神奇吧,是不是很神奇,那如果我们再来举个例子,比如说现在呢,我们查到的是100,假如我们查到的是100啊假如啊,比如我们现在换了,比如。
11:10
我们查找的值是多少呢?是100,那么我们来看一下这次定位需要多长时间,那么还是me的,如果是100的话呢?呃,Ne第一次仍然是零,再加上各位同学请看哈,呃,Right减left right减ne应该第一次仍然是99减去一个零对不对?再乘以什么呢?各位朋友再乘以。Find的值减去left,那find的是100,你要找到100减去多少呢?减去一个一啊,再除以多少呢?除以这个值,这个值是不是仍然是100减去二减去以。呃,这一个一二,也就是说这边仍然是100减去一个一。那减去一个一,这边这个值等于多少呢?就等于零加99。
12:03
乘以一个99,再除以一个99,各位同学请看结果是多少?零加99,呃,99乘以99再除以99,是不是就是零加99啊各位朋友。是不是99,你99乘以九,再除以99,不99,那最后结果99,诶各位同学有没有发现一步定位。是不是很神奇,因为它这里用了一个小算法,就是自适应来找我们密,那显然如果用叉值查找算法的话呢,在对于这种数据比较连续的情况下,而且你数据量还比较大的情况下,我们这个差值操作算法呢,就凸显出它的优越性,因为它定位会比较快。我们很快就定位我们要找的数,明白这意思吧,所以说经过这个案例呢,大家就应该对我们插值查找的工作原理有一个比较深刻的理解了。好,那大这个原理给大家讲了以后呢,下面我们就要准备用代码把这种方式给各位朋友实现一下,但是不难,因为它整体仍然是按照我们二分这个方案来玩的,明白这意思吧,好,那关于差值查找算法的原理和这一个推导过程呢,先给同学们讲讲解到这里。
我来说两句