00:00
各位朋友,我们根据刚才的思路分析,将二分查找的算法给大家用代码实现一把来走一个,那search呢,我们先建一个类叫binary啊,Binary search。E ch没有毛病吧?把主方法勾上。那同样刚才呢,我们已然,我们已然把这个数组准备好了。那数组呢,我们就是这样一个数组,注意啊,二分查找要求数组必须是有序的,注意听这里面啊,注意。注意二分使用二分查找的前提前前提是什么?前提是该数组数组是有序的。啊,有序的,至于是从小到大还是从大到小,呃,这个无所谓,但是注意啊,如果是从小到大,是按我这个思路来走,那如果是从大到小,你这个条件刚好要反过来,比如说大于它,你就应该向左边打,小于它应该是向右边走,明白我的意思吧,因为你你你顺序跟我不一样了嘛,对不对。
01:10
那我把数组呢,给各位朋友拿过来。就以刚才。讲的这一个数组为例来进行测试,格式化一下。格式一下,好朋友们,那现在呢,我就写上这个二分查找。查找算法来public static。啊,返回下标吗?说说我是一个binary search。那你要干什么事情呢?各位朋友,你要把这个数组传给我没有问题吧,各位,因为数组是引用类型,所以它递归的时候一直在用同样一个数组,然后呢,你得告诉我right是不是刚才left已经说好了呀,然后还有一个什么呀,Right说好还有一个什么,你要告诉我你要查找的只是什么find value,这个没问题吧。
02:00
说这几个条件你必须给我。必须给我好的,那现在呢,我们把这个地方稍微的做点注释。好,刚才讲了,这是呃数组。输出这边是呃,左边的该左边的在查找时左边的索引。左边的索引,那这边显的是怎么样?右边的索引没问题吧,这个是要查找的值,要查找的值没题好,最后返回的是什么呢?是如果找到,如果找到就返回。下标。下边如果没有找到呢,如果没有找到就返回,我们就返回什么呀,就返回A返回一个负一,负一代表没有吗?好的同学们来走一个。首先呢,我们根据刚才的思路,我们先要拿到哪个呀?我们先要拿到中间的这一个下标来走一个,那就是in mid,等于什么呢?Left,刚才是不是已经分析过这个了,加上right。
03:11
然后呢,除以二没问题吧,然后把中间,诶把中间这个值我们也拿到mid value等于谁呀R。谁?我们的密没问题吧?那现在呢,我们就来进行判断,如果我中间这个就是我要查找这个值。它大于。它大于刚才我们讲的是按顺序来吧,如果M的它大于中间这个值,好的,那大于我们这个咪的。Value。那在这种情况下呢,我们需要向哪个地方递归压,我们需要向哪里向右递归?向右。向右递归,再说一遍啊,现在之所以向右递归,因为你是从小到大。所以说我要在右边去找有没有这个数,怎么体现出向右递归呢?Very easy,把这个写过来,把数组传进去。
04:06
把数字传进去,那么向右递归,那向右递归的话,相当于说呃。我们这个要移动到这边来。是这意思吧,那你这个要移动这边来,那这个下边的值应该是多少呢?是不是就应该是它左边就变成幂的。Mid加上什么呀,一。试一试吧,然后right不需要变化。因为还是吗然find value传进去。是不是最后呢,这边返回一个值就可以了,Return就行。对不对,好,那么问题来了,那还有一种情况下,就是s if,如果我们要查到的这个值啊,它小它小于幂的。Value说明什么呢?我们需要向。向这个是向右,那这个就应该是向左了。对不对,那这个就应该向左递归。
05:00
向左递归,向左递柜,那向左递归呢,跟刚才的呃类似,咱们写下byary search。数组传进去left应该是什么呢?Left,什么left就是left,右边是什么呢?就应该是mid啊,向左啊,现在是向左,向左的话就是mid减一。是吧,同学们是幂的减一。OK。这是向左立柜。那么还有一种情况下呢,就是你很幸运找到了,那找到了过后呢,我们就不废话,直接返回一个负一,呃,返回me。这个索引就可以了。来,我们把这段代码给大家进行一个简单的测试,看看现在行不行。现在行不行?来,我们先得到一个result index。结果的索引,那么binary。找把数组传进去,这个应该是零,这边是什么呢?R点认,因为它最最初的时候r.N减一嘛,值是多少,比如说我找一个一。
06:01
来同学们,我们看一下格式化一下,那现在呢,我们把这个结果输出来看一看啊走一个。那么,System。把索引打出来。Index等于多少呢?加上result index,我们运行一把。我们可以看到此时此刻等于零完全的正确,为什么呢?因为你这个一就是零嘛,好,我们再找一个最边上这个数1234运行,我们发现呢,也没有问题,下边为五,我们再找中间一个数,各位中间一个数是比如说89吧。89我们看89能否找到,89我们发现呢,没有任何问题三。啊,0123对的,但是同学们看到我们这个代码呢,存在一个问题,大家知道什么问题吗。有没有发现我们这儿没有考虑找不到的情况?那如果说我在这里找一放一个不存在的数,你们就会发现它会出现死地归你看啊,找一个88,你看这里面你。
07:05
你没有,你是这个。嗯,这个向右递归,这个向左递归,这个是找到,那没有找到你你没有考虑啊,就是我说的这个情况,你没有考虑啊,你就是找到了你就结束,但是没有找到呢,好,如果我们写了一个不存在的一个数,你会发现这里就会出现一个死循环。大家看。各位朋友请看这里已经已经出现了sta overflow error什么意思?死,死地位了。原因就是刚才老师说的这个问题对吧,那现在呢,我们应该有一个判断,什么情况下我们就要结束递归呢?把这些当当left left大于了right时。说明说明。递归完毕,递归整个了,整个数整个数组了,但是没有找到,但是没有找到。试一试吧,那没有找到你是不是就应该直接返回一个。
08:02
负一就可以了,那就说如果left它大于了。那这个情况下说明没有了,没有我们就不要再犹豫了,返回负一就可以明白这个意思吧,好,这是老师写的这段代码,我们再来玩一把,这是一个88,看看还有问题没有,走一个我们发现呢,没毛病了,马上返回复议,因为你这个88不存在,代码就这样结束。代码中因素,也就是说我们一个二分查找呢,就写完了,写完了。OK,那关于二分查找呢?呃,最基本的写法就是这就这个地方,待会儿呢,我们还有一个案例是要求对二分查找进行一个升级的处理。进行一个升级处理,那我这这个二分查找的基本写法,我们先给大家讲解到这里。
我来说两句