00:00
同学们,我们接着来讲数据结构和算法的,下一章叫程序员常用的十种算法,那也就是说从这一个章节呢,我们重点就是讲的算法了。换言之,就是把前面我们学过的这些数据结构使用到一个实际的应用场景去解决一个问题。那么在解决这个问题的时候呢,咱们就抽取出来一个算法。重点就算法了,OK,那么我们这讲的十种算法有哪些算法呢?我们一个一个的来讲,首先第一个要给他讲的是二分查找算法。那么同学们会觉得比较奇怪,说啊,老师,那二分查找咱们不是前面讲过吗?是的,前面我们是讲了一个二分查找,当时我们用的是递归的方式来进行二分查找的,对不对?那么现在呢,我们讲的是一个非递归,而且二分查找呢,它也是一个比较。经典的一个算法,所以说在面试的过程中呢,也有可能别人让你写出两种方式,一种是递归的二分,一种是非递归的二分。
01:07
所以说呢,我们来看一下非递归,非递归的二分查找,它是怎么做的好的,那么二分查找呢,只适用于从有序数列中查找。比如说数字或者什么要有序,那也就是说你在进行之前呢,需要先将数列排成有序,再进行查找。二分查找的运行时间为对数时间,即它是一个什么呀?它是一个对数阶log,以二为底,N的一个对数。那么我们简单分析一下,即查找需要的目标位置最多只需要LOG2以N为底的一个对数,以二以二为底的N的一个对数,那么假如我们是从零到99的一个数列及100个数列。去找目标数三次,那么我们需要查询的步步数最多为这么多次,那大概是多少次呢?大概是在,呃,大概最多只需要七次,因为二二点六次方,2.6次,就说100这个100这个数呢,它是介于二点六次方到2.7次方之间,所以说只要是七次。
02:17
只要使用七次,那么就一定能够把这个数找到,所以说你们可以看到二分查找的它的时间复杂度其实就是log以二为底的N的对数。好,这是对二分查找的一个介绍,那么下面呢,我们就来给大家演示一下二分查找非递归的。一个代码实现,嗯,关于二分查找,其实前面我们已经讲过了,那这时候我们就不再做过多的思路分析,我们直接上代码好吧,大体的思路就是找,找到中间这个数比较,如果中间这个数比我要找的数大,那么我就向左边查找。如果中间这个数比我要查找数啊,要比我这个数要小,比我的这个数要小,那么我就向右边查找,因为你你比我小的话,说明我要找的数应该是在这个有序数列的右边,注意啊,前提是你的这个数组是升序,如果是降序,就要把刚才我说的向左向右颠倒一个个。
03:19
好了,同学们,那思路到这儿呢,我们就来开始用代码给大家走一把。那这是这样子啊,因为我们要讲十个常用算法,哪十个算法是不是前面我们已经讲过了,所以我们已经做过课程介绍,要要讲分制算法。分支算法讲完了过后呢,要给要给同学们讲动态规划算法。这个动态规划算法讲完了,我们给大家讲KMP算法。然后是贪心算法,然后是什么算法呢?普里姆算法,然后是。这个克鲁斯卡尔算法,然后是哪个呢?迪杰斯特拉算法,然后再是我们弗洛伊德算法,弗洛伊德算法完了过后,我们还有一个马踏棋盘算法,也是也叫其实周游问题的一个算法,好,那么我们现在呢?呃,做了一个介绍后,我们现在直接就把刚才说的这个要求,哎,刚才的二分查找给大家演示一遍就可以。
04:22
好,回到这,我们用代码跑一遍,那么因为算法比较多,所以说我新建一个项目。专门说我们的算法,好吧。分一下,那么算法这个英文单词是all reason。Algorithm。对不对,那么我们就用这个作为我们的项目的名称,下一步。Finish。好,同样的道理,我们建包,我们建包来建第一个包,com.at硅谷点,我们第一个算法呢,是一个二分查找。二分12C,但是是一个不是一个递归的,所以说我写个no。
05:06
好,名字有点长哈,没关系,那现在呢,我们就在这里面建上我们的这个类,这个类呢,我们就叫binary binary search no什么呢。C,那我就简写了好吧。把这个主方法勾上。嗯,那么我们首先呢,先把这个数组写出来啊,直接写方法吧,咱们写一个二分查找的非递归实现,非递归实现OK。那开始写public static static void。呃,不是贸易的了,咱们返回下标就可以了,Bary bary search,好,就简单写到这里,那么你把这个数组给我传过来对不对?然后呢,把你要查找的这个目标数给我,Take。
06:02
好的,我在这里呢,把这个方法做一个简单的说明,二呢,显然就是你要代查找的,代查找的数组没问题吧,这个是查需要查找的,需要查找的这个数没问题,返回的是下标。返回对应下标,下标啊负一表示没有找到,表示没有找到,好,那下面我们开始写了。呃,首先呢,我们先定最低的那个,就是左边的那个对吧,也可以这样写left等于什么呢?零初始化。那么right呢?Right,我们等于数组的这个N,是不是减掉一个一没有问题吧?现在我们找到找到它一个while循环退出的条件就是。只只要是这样子的,只要我们left小于等于你的right,说明什么问题,说明我们可以继续,哎,只要这个条件满足就可说明可以继续查找,没问题吧。
07:12
继续查找,那现在呢,我们就把中间这个值给呃,中间这个索引拿到,中间这个索引呢,显然是我们的ne加上我们的right。干right干什么呢?除以一个二。是不是同学,同学们,那现在呢,我们就做一个判断,如果你这个数组。的什么呢?这个中间这个数幂的这个数,它大,它等于这个,比如它等于我们的target。他如果等于我们这个target,就是我们这个目标找到了,找到过,这就不多说了,咱们直接mid是不是,那么L如果说我们再来看一个条件啊,再来看条件。LE。
08:02
如果说你这个怎么样,它大于target。OK,它大于了,就是不是等于,而是大于,如果是大于的情况,我们应该怎么办呢?同学们想一想。应该怎么办?是不是我们要进行下一次的工作,因此这个时候咱们不是递归了,咱们得把这个right变成什么呀?把right等于mid减掉一个一,这说明向哪里呢?需要需要向。向左边左边查找。注意啊,是你的中间这个数比我大,我就向左边,因为我们这个现在默认这个数组是升序的,对这边还要写清楚啊。呃,我们说二位是申戌。升序排列。排序,如果是降序,这个地方要反过来写,还有一种情况就是S了,对吧,你要么是等于,要么是大于,还有一种就是要么是小于,那如果是小于的话呢,同学们下一步我们应该是no啊,不是no应该是ne,等于什么呢?各位同学是mid加一。
09:16
这说明需要向什么方向,向右边查找。是这样子吧,好。整个这个就做完了,如果整个while循环,它没有return,它没有进行这个return,那么我们就知道找不到了,就一个负一代码就写完了,那同学们我们试用一下吧,我们测一下。测试,那测试也很简单,我们把这个数组放过去,刚才呢,我们已经有一个测试数组,就是这样一个数组,对吧。把它写好。没有问题,写好以后呢,我们来进行一个简单的测试,Int index等于binary search,把数组放进去,我们要找的这一个数呢?是什么呀?同学们,我们要找的这个数。
10:08
啊,我们来看看这个地方要找的数是。想一想啊,咱们要找的这个数呢,是我们设置为一吧,假设是一,对不对,假设是一,OK,那如果是假设为一的话呢,我们看看能不能找到这个数走。Inex等于加上index。对不对,那理论上应就说,如果不是文体不是问题,它应该返回一个零,对不对,运行。好,我们可以看到呢,它返回了一个零,Very的OK,好,我们再来找一个数,就找最后这个数100对吧,那这个时候呢,它返回一个下标等于六也是正确的,因为下标100确实是六,我们再找中间一个数吧,比如说八。
11:01
都测一下八,运行之我发现八这个数呢,找到下标为二正确的,我们再找一个不存在的,比如说负八,看看这个会返回什么,那负八应该就返回负一了,是这样子吧?同学们好,我们运行之我们可以看到呢,返回一个负一,代码写完,而且验证的确是没有问题的。好的,那同学们这样子,我们这一个关于二分查找的非递归,咱们就讲完了,也比较简单。对吧,比较简单,理解起来应该说比我们的这一个叫做递归的形式还要好理解一点,效率也是很不错的,因为他们用到递归嘛,那就比较节省我们这个,呃,开辟占空间的这个这个开销了,好同学们,那关于这个我们称之为二分查找算法呢,非递归的形式,就给大家讲到这里,我们把东西进行一个简单的板书,来打开我们的这个笔记,把这块稍稍的整理一下。笔记打开。OK。
12:00
打开这里。那么我们刚才讲的内容呢,是一个二分查找的非递归一个算法来走一个。好,我们先把这个标题拿过来。这块讲的是第下一章叫程序员的。常用十种算法这个章节来写到这里,跟着我的思路。程序员常用的十种算法第一个程序算法就是我们所说的二分查找非递归。二分查找的非递归形式,好的,那首先呢,我们对二分查找非递归做了一个什么呀介绍,是这样子的吧,做了一个基本的介绍,然后说了一下二分查找非递归的。它的一些特点整理到这里了,把这个讲完以后呢,我们就直接上代码了,因为前面关于二分查找的这种思想在。前面已已然说过,所以说这里呢,我就没有再啰嗦了,代码好,思维很简单,代码直接给大家拿过来,代码在哪里?就是刚才我们在这块写的,直接放过来即可。
13:10
好了,朋友们,那关于二分查找的非递归算法就给大家聊到这里,这个一定要记下来啊,虽然简单,但是呢,他在我们面试的过程中,其实出现的频率是比较高的,所以高频。的一个面试或者是笔试的一个题,好的同学们,到这里我们就说,呃,二分说到底。
我来说两句