166_尚硅谷_Go核心编程_二分查找的思路分析.avi原创

那我们再来看一下二分查找。我们看二分杂找怎么完成好。首先呢，我们把二分查找这个要求先给大家看一下，他说请对一个有序数列进行二分查找。那也就是说二分查找呢，它有个前提，就是它是一个有序的，那有序就意味着要么是从小到大，要么是什么呀，从大到小。那么他说输入一个数，看数组是否存在此数，并且求出下标，如果没有呢，就提示没有这个数会使用到递归。好，嗯，我们还是老规矩，同学们就说我们在去编写一段程序的时候，我们首先要进行什么呀？思路分析来，我们看看思路分析。就说我们叫做二分查找的，二分查找的思路分析，如果没有思路没有分析，那同学们我写出来过后呢，大家也看不太懂，注意听，还是老规矩，用这个Excel表来画想。

OK，请大家先看。这里有一个二维数组啊，这里面有一个数组，我们先把这个数组呢拿过来。就以这个数组为例，好吧。这有个数组。那么这个数组。这个数组我们可以看到目前是个有序的。对吧，这是一个假设，我们叫二。这个数组，这个数组呢，目前是这样一个样子。那么。从这里我们可以看出。二是一个有序数组。没问题吧，有序数组，并且它是从小到大排列。没问题，好，现在呢，这个这个二分的思路就来了，二分查找的思路是这样子的，第一个他首先要保证是一个有序数组。

好，然后呢，第二步，第二步呢，它是这样做的啊，同学们注意听它呢有两个下标。我用两个不同的箭头来表示，比如说这个是绿色的箭头，它表示一个下标这边。又表示另外一个下标，那么这边的下就是二分，它是怎么做呢？它是从两头找中间这个数，我们姑且把这个下标叫做。Left left index。就是这是下标。我们把这个红色呢。把它叫做什么呀？把它叫做right。Index。好，现在呢，我们来谈第二个思路，比如我们要查找的数是。好，我们先规定一下啊，比如我们。要查找的注意听，查找的数是什么呢？是叫做find value。

好吧，我们就取个名字叫find value好，开始提思路，注意听。首先它这样做啊，二分法查找法是先找到注意听先找到这个中间的。注意听中间的这个下标。那中间的下标就是left index加right index除以二中间下标我估计叫mid mid。D Le，它等于什么呢？它等于left。Index加。加right index。除以二。是不是这是中间的下标了，找到，然后，然后让什么呢？让中间这个下标的值中间下标。

下标的值和范的value进行比较。好，注意他一旦比较就有三种可能，哪三种可能第一种。就是。这个中间这个下标对应的值大于find value。第二种就是中间这个下标对应的值小于value。第三种相等。是不是好，这里面就有三种逻辑，如果，如果什么呢？注意听啊，你。是不是就是中间这个值啊，它大于find value。请问这说明什么？这说明就是你要查找的这个数。飞婷，你要查找的这个数。可能或者说如果存在的话，他也应该是在哪一边，是不是在这个密的，就是在中间这个下标的哪一边左边，因为你是从小到大排的。

你现在是不是从小到大？那如果说这个条件成立，就应该。就。就应该向哪边查找呢，向。这个这个left。Index到哪个之间查找到这个mid。DD Le减一这个区间进行查找能理解吗？是这个区间到这个区间进行查找。因为你你中间这个数你大于别人嘛，你大于别人，你又是从小到大排列的，所以说如果这个find value在的话，他也应该是left index，这这边下边到mid减一这个这个范围去找。这个能理解吧，你比如说吧，比如说我现在查找的数是。四八。如果八跟中间这个数进行比较，89是不是你中间这个数大于八呀，大于八的话，说明我要查找的八应该是在。

现在老师高亮的这个范围，所以说你就应该向left index到mid的减一这个范围去查找，是这意思吧。那当然还有一种可能性呢。还有一种可能性，就是你中间这个数怎么样小于范的value。那说明你要查到这个范有外范应该是在哪个范围呢？那就应该是mid。加一。到哪个范围，到right left这个范围。是这样子吧，Right in范围。问题还有一种可能性。就是2.3就是找到了，如果。如果你中间这个值。刚好等于什么？刚好等于要查这个数，那就恭喜你找到了。

就找到了。就找到。是不是就找到了呀，那么这个逻辑就是老师说的这个逻辑，它是要周而复始的执行，也就是说。比如中间这个数找到了，诶一比较，假设我有，我有一个箭头。还有一个箭头是表示中间这一个下标。我有三个吗？左中右好，假设中间这个值。如果是中间这个值。呃。比你要查的数大，那就到哪边呢，就让这个标，这个标往这边移动。然后中间这个值是不是就移动到这来了。是这意思吧？那也就是相当于说，为什么管它叫二分呢？就是中间这个数一旦不是马上我们就把这个数组砍成两半。你要查找的话，只能是在这一半，或者是在这一半，所以他这为什么这么快呢？就是因为它是折半查找，你打个比方，你打个比方，我们还以这个为例。

你原先在这个地方一共有几个数，一共有1234566个数，假设中间这个值我们是，呃，算下来是是这个值对吧，假设是这个值。那如果这个八和中间这个数一比较不相等。那么八就应该是在这边移在这边好，我把这个left往这边移动，中间这个值一加就是这，你看这一下子。就把这边这一半呢，就直接抛去了。为什么他二分查找速度快呢？就是这样子的，那当然前提是要求我们这个数组是一个什么数组，是一个有序数组，如果不是有序数组，大家看我们这个这个分析就是不对的。因为它如果是个无序数组，你就没有办法判断，就就算你中间这个数大于这个值，你也不能说它一定是在这半了，为什么？因为它是无序的。但是如果是有序的话，我们就可以用这个来做，对不对，好，我把这个还撤回去。

好，这个思路大家清楚了吗？如果清楚的话，最后这一句话，这个逻辑就是这个逻辑会周就会递归的执行。如果你这挪到这边来，如果还不是又折半又折半又折半，所以说D还有一句话。上面的。上面上面2.12.2。2.3的逻辑会递归执行，能理解这意思吧？最后有一个非常重要的分析，什么时候。我们就认为他找不到呢，就说怎么样才认为他找不到，就会退出这个递归去查找，就说这个问题摆在大家，大家想想想想。什么？想一下想一下怎样什么样的情况下啊，怎么样的情况下就说明找不到。

找不到，请同学们思考。也就是说这个地方就是要大家来分析什么才是退出，就是要分析出分析出退出递归的这个条件。这点非常的重要，如果我们没把这个条件分析出来，我可以负责任的告诉大家，我们这个二分写出来也是个死规，一定会死循环在里面。大家想想。分析出退出地位的条件，能给我分析出来吗？就什么情况下我们才认为他找不到了？各位同学想一想。哪种情况是不是。我们这个向右，向右边的这边递归，这个这个指鼠标啊，这这个这个箭头假设往这边移动了。这个左边下边它一定会往这边移动，就是说它始终是越靠越近，越靠越近。最终有一种可能性，就是左和右他们都相等了，还能进行一次比较。

如果说我们发现左边，左边这个还比右边这个大了，那就说明的确是找不到了，因为它最多只有最后一次比较，就是左边的下标和右边的下标相等了。如果还不还不是这个数，那就说明真的找不到了，因为你再往这走的话，你的这个像，因为你已经把它这个二分就已经已经全部找全部扫描了一遍吗？如果我们左边这个下标和右边这个下标已经指到同一个数了，它还不是，那就意味着什么呢？那就意味着我们这个左边的我们我们左边这个绿又哦这个这个右边这个继续往往左边跑，而左边的继续往这边跑，那就出现一个什么情况，左边的下标还比右边的下边还大了。这个条件一旦出现，就说明真的找不到了，也就是说他最后一次比较的只有一种可能，就是两个。两个一个，左边的下边和右边下标相等，这是最后一次比较。如果还不是好。

就不要再比较了，肯定是找不到了，能理解这个意思吗？大家想一想，是不是老师这个这个分析啊。好，我们来分析退出的条件是这个，如果。如果left。Left index大于。Right index说明什么？这个条件一旦执行就说没找到了，就找不到了。就可以退出了。就可以。这个条件一定要分析出来，好了，同学们，这是老师对二分二分查找的一个分析，下面呢，我们就要把这个思路。我们就要把老师刚才讲的这个思路转换成我们的代码。好，来了。这就是编程，编程其实一直在做一件事，思路变代码。如果你没有思路，说实话代码很难写出来，当然代码这块呢，主要考考察我们对语言本身应用的是否到位。而这根线。

就是你的思路和代码要。很快的整合在一起，或者是联系在一起，这就需要长期的锻炼。就是你写代码写多了，你思路一有，你代码马上就反应出来了。条件反射对不对，但是如果说你锻炼比较少，可能你会有思路。但是你写不出来代码，比如说。有一些大学的学数学的，学物理的学生，其实他们的思维很很好，很很很很多算法，很多想法都有，但是他们就是写不出来代码。有些计算机系的同学呢，他代码写的很熟，但是他思想又思路又稍微差一点，比如他没有像数学系的那些学生，他的思是他的算法那么多，所以他也很难写出算法，能理解吧。这两这两者缺一而不可，好了，不管怎么样，我们已经分析出来了，来，老师把这个二分查找的思路分析给大家画到这里来，能理解吗？

思路分析有了。好好的看一下，有了思路分析好同学们，我们下面要做的一件事情是不是非常简单了，做件什么事？就是把这个思路分析写成我们的代码，下一步呢，就是要做这个工作，二分查找的代码实现。代码实现好，那关于二分代二分查找的代码实现呢？我们放在下一个视频里面为大家讲解，大家先把思路捋清楚。