JavaSE进阶-105-二分法查找原理原创

来看一下二分二分法查找啊，嗯，我在下我去新建一个class，我们叫数组的search。嗯。换一个名字吧，改个名啊叫。数组工具行吗？这这能看出来吧，数组工具类。啊，自己写的啊，不是散的啊，对自己写的。然后呢，我们来看一看什么呢。看一下这个关于什么呀，关于查找算法中的二分法查找。二分法查找啊，首先呢，就是比如说现在我有一个什么呀，就是十十一十二十三十四十五十六十七十八十九二十。

啊，然后这个数据对吧，哎，通过二分法查找。对吧，哎，找出找出18。18啊，这个元素的下标你怎么找啊各位。所谓的二分法是什么意思啊，就相当于说他不是从第一个位置开始找了，如果你第一个位置挨着比，挨着比，挨着比，挨着比挨着比，这个效率比较低，怎么做呀，把这堆数据怎么着一分为二。一分为二啊，你比如说十这个元素，它的下边是几啊。那下标是几啊？下标零是不是0123456789，这个下标是多少啊？是十吧。是不是下边是十呀，哎，下边十，那这个时候呢，它怎么做呢，就把这个零干什么呀，加上去谁呀，这个十加完这个十之后呢，让它除以二。

除以二之后呢，哎，得出的这个值就是中间那个元素的下标啊，就说中间元素的什么下标，那这个中间元素的这个下标是多少呢？零加十是十十除以25。这是五啊。是不是好，那么这个时候怎么做呢？拿着这个中间元素和我们的目标元素对比。啊，拿着中间这个元素和目标要查找的元素进行对比，明白什么意思吧，你现在呢，假如说这个数组它是一个。AR数组啊，AR数组我们要通过这个AR数组当中啊，通过二分法查找，找到这个18这个元素所在的这个下标啊，二分阀就是说把第一个位置的下标记下来，把最后这个元素的下标的位置记下来，记下来后怎么着啊，给它加，加起来之后除以二，除以二之后得出中间这个元素的下标，拿到中间下边之后呢，就是五呗，对吧？五的话，012345是不是就是AR5啊，中间这个元素是啥呀？中间元素是什么？

啊，是AR几啊，因为下边是五啊，所以你AR5，然后接下来AR5是谁，就是15啊对不对？好，那么我问大家15是不是小于十八十八是什么被查找的元素吧，这说明被查的元素在右边还是在左边各位。就被查找的这个元素。在中间这个元素的右边还是左边，就通过这个得出一个结论是什么呢？就是被查找的元素啊，被查找的元素啊，18在什么呀，在在目前中间元素15的什么，哎，右边哎，通过我讲到这儿你就知道了，二分法查找只适合于从小到大排序的。从小到大排序的数据对吧。

如果你这个数据的顺序是乱的，你这个二分法查找是不是就用不了。二分法查找是建立在排序基础之上的，注意啊，我在这里呢，我写第三点，先先写上第三点啊，二分法查找算法是基于什么呀，排序的基础之上。明白吧，排序的基础之上啊。嗯。没有排序的数据是无法查找的啊，没有排序的数据是无法查找的啊，所以这个呢，跟刚才这个还是有区别，你刚才这个说白了就是这个数组，你这你是乱的对吧，他他要找的话也能找到，但你如果采用二分法查找的话，首先你得干什么呀，你得排序。排序啊，排完序，从小到大排序，然后你才可以按照这种规律去找零加十除以二是吧，哎，除以二之后怎么办呢？我们就达到中间元素是五，下标是五，那就是15呗，那15这块一分析小于18，小于18，那证明18是在我们中间这个元素的右边，那么我问大家这个时候我们是不是应该把开始下标改成六啊。

你开始下边你看012345吧，这是不是六啊。对吧？啊，因为你在15的右边啊，所以结束下边你不用变，开始下边是不是得变一下。对吧。哎，被查找的元素18在目前中间元素15的右边。啊，所以，所以开始元素的下标从零变成什么？从零啊变成六。变成五加一。啊，不知道大家理解不解，这个你原先的时候开始下标不是零吗。对吧，这个时候开始下边到这了，这是什么是五啊五加一啊。

五加一啊，五加一是六，那么这个时候我们再计算一个中间线标啊，再重新计算一个中间元素的什么下标，那么这个时候再重新计算是怎么是开始下标是五加一啊现在啊，对吧？那结束下标是什么呀？结束的下标还是这个十啊。对不对，所以应该是六加上去十，然后让它括起来除以二。对不对？六加上十，然后这不是开始，这永远都是开始嘛，加上什么结束吧，加上结束下边，然后除以二，除以二得出的这个结论是多少呢？哎，16除以二是八。对吧，好，那么大家看啊，那么现在什么呢？这个八下边八下标对应的元素A8对应的是多少啊，元素对应的元素AR8是多少啊。

哎，就是18。对吧，哎，就是18那。找到的中间元素正好和被找的元素18相等。啊，表示找到了。下标为什么呀八。这样的一个一个情况啊，我不知道大家有没有理解啊，我再随便再再来一堆数据，我临时建个文件啊，在这给大家简家说一下啊，别在这儿说了，这样吧，我把这个D盘把cos打开，零二打开打开，然后把这个叫做D24的一个课堂笔记打开啊，我在这个里边接着去给大家说一下啊，说一下啊，这是一个选择排序，再往下。二分法查找各位啊，二分法查找，那么首先第一二分法查找建立在排序的基础之上啊，第二二分法查找啊，效率要高于什么呀，这个一个挨着一个的这种这种查找方式啊。

高于哎，一个挨着一个的啊这种查找方式第三，那么二分法查找原理是什么？再来一堆数据各位啊十二三。23啊，然后56，然后89啊，一百一百一十一二百二十二啊，然后接下来比如说235对吧？啊，五百六百行吧，就这么着啊，我们要找出什呢目标啊，注意听目标找出什么呢？找出600行吧，找出600的下标。

找出这个600元素的下标，怎么找呢？首先它开始位置是零下标。注意啊，这个位置是一个开始标是一个零，下边0123对吧，456789好各位，这个是不是下边是九啊。九下标吧，下标是九啊，这是，那么这个时候我们是不是零加上去九对吧，加上九之后呢，让它除以二。除以二是多少呢？是不是四啊，是不是四啊，四是什么？是中间元素的什么下标明白吧，哎，零加九除二是四嘛，那四是中间元素下标，那现在假如说这个数组是AR数组，那么这个时候呢，我们现在的AR4这个元素就是中间元素啊是不是，那A401234是不是，哎，R4是不是100啊，AR4是100啊四。

是100是100，那么一百一百干什么呀？是小于什么，我要查找的是什么呢？目标是什么呀。各位，我们查找的时候目标是600是吧，是不是100是小于600的。是不是小于600，那么100小于600，这说明什么？说明被查找的元素在什么，在100的右边对吧？那么此时开始下标变成多少各位。开始下边变成四加一，因为你原先中间元素是什么？是01234嘛，这个是不是小于600，所以被差的元素在右边嘛，是不是被差元素在右边的话，那你现在开始找的话，你想一想是不是就是说你你你你应该从这开始往后找这一堆对吧。

是不是，哎找这个二分法就是说你不用一个一个去找了，你从现有的这个数据里边分出来一半，对吧，你先试探着，诶拿一下说哦100，哎小于什么呀，哎，我们六百六百证明在100的右边，那这样的话，前面这个数据就不用便利了呀，这省多少事啊是不是？哎，你拿着后边这个数据再给他折半。折半再折半，明白什么意思吧，后边这个数据折半的话，那你开始下标是是多少，你你中间元素下标是四嘛，四的话开始下边就变成五了呀，对不对？哎，二分法查找再提一下啊，叫折半查找各位啊折半查找，那么此时呢，开始变开始下边变成四加一，好各位，那么再来各位啊，四加一是多少。四加一。这是一个什么呢？五吧，是不是开始下边变成了五啊，那五加上结束下边各位结束元素的下边是九啊。

是不是九啊，对不对，哎，五加上九，然后让它再去除以二，好得出的这个中间元素下标啊是几啊，五加上90是十四十四除以27，那这个七呗，那就是现在就是中间元素的下标是七，那么AR括号七你看这个。这个值对应的是多少啊哎，AR7啊是这个元素就是中间元素啊，现在就是中间元素，就是你剩下的这波元素里边，中间元素这是401234567，好，大家看是不是正好是235。235对吧，哎，235，那么235小于600呀，是不是，哎小于600，那么这个时候这说明什么呢？说明说明。

被查找的元素在在什么呀？在这个235的右边啊，那么此时开始下标。又进行了转变啊，你这个地方是七，应该是七加一对吧。对不对，七加一是不是八呀，各位八加上谁开始下边就变了呀。对吧，哎，因为开始你你找这个，这个不是小于它吗？开始下面是这个吧。是不是这个呀。啊。他原先是。嗯。是七嘛，是不是，然后再加上一是不是八嘛，八是这个。八加上多少啊？结尾是多少九吧，八加九除以二再折吧，它剩下的这堆数再去折吧，啊八九十七十七除以二。

等于八，各位啊，等于八。八加上九等于十七十七除以二是八，好了，那么AR8现在拿到的是谁？各位。八拿到的是不是就是500对吧，那500是不是还是小于多少600吧，对吧？那么开始元素的下标又发生了变化，对吧，是八加一啊。对不对啊，因为你现在500还是小于600嘛，所以它是八加一八加一是九啊，九加上最后这个元素的下标是九嘛，那么这个时候呢，括起来，然后再除以二，最后的这个结果就是九，那么A9这个元素是谁？是600对吧？哎，是600啊，正好和600怎么着相等啊，此时找到了就是说。

是这样的一个一个情况各位啊，就是它这个二分法查找，就是说我通通过这堆数据里边，我去找中间的这个元素，找到之后呢，我看看这元素是呃小于还是大于，如果说是小于的话，就从右边开始找，右边找的话，这堆数据就开始这个元素的下边就变成它了，那就不是这个位置了啊，那还有一种情况，各位，如果你要查到56呢，或者说你要查23呢，或者说你要查这个十，这个元素所在加标呢，对吧，那这个时候你同样折半，折半之后呢，找到这个元素，这个元素比它大。比它大的话，大家想一想，是不是应该在这个元素的左边啊，如果在这个元素的左边的话，开始元素下标不用变，结束元素下标，是不是你中间这个元素下边减一啊。

中间这个元素的下标减一是不是就是你结束下标，总之永远都是你开始加标，加上结束元素的下标，然后再除以二，除以二之后怎么着啊。哎，找到中间元素，拿着中间这个元素怎么着，哎，和你的尿查的目标元素对比啊，你目标查这个元素，哎，对比一下，直到你相等的情况下，我们就算找到了，这就是二分法查找，就是我们的查找。为了提高效率，它采用的是什么？就是这种方式，这是一根一根一一个一个一个数组啊，假如说他怎么办呢？他通过这切开。对吧，切开之后怎么办呢？它这一块啊，通过这一块去找了，或者也有可能是通过这块找了，那么通过这块去找的时候呢，他又进行了折拌。明白吧，哎，折半之后如果他还是没有找到，它有可能折半之后他要找到这个元素在哪啊，哎，它有可能在这个位置上。啊，在这个位置上，那么如果在这个位置上的话，他就怎么着再去哎折半。

哎，再去折拌，折拌之后呢，哎，它有可能找到元素啊，它又缩小了范围，这个缩小的范围是哪？哎，有可能是这。那么这个时候呢，他再通过这儿干什么呀，哎，折半。折半啊，这颜色变一下折半，那折半之后呢，它有有可能怎么着啊，哎，它这个数据啊，啊是在这一块。啊，是在这块这个区间。明白吧，啊，这个区间，然后慢慢慢去缩小区间，最后呢，就找到这个，呃，被查找的这个元素，它的这个下标了啊，直到说你拿到的中间这个元素就是最后怎么就算停了，中间这个元素正好和你要查的那个元素怎么着。是相等的，这就是二分法查找的一个终止条件。终止条件。二分法查找的终止条件。就是中间一直怎么样折半啊，一一直折半啊，一直折半。

直到什么呢？直到中间的那个元素恰好。恰好是。被查找的元素。啊结束明白吗？啊结束行了，那这块的理论呢，我们就讲到这儿。