076 - Java入门极速版 - 基础语法 - 常用类和对象 - 数组 - 二分查找法

大家好，我是海波老师，接下来我们来讲一下Java数组中数据的查询，那之前提到过啊，数组中的数据啊，都会有一个下标索引，它从零开始，它可以用于快速定位数字中的位置，就好比抽屉中有五个小格子一样，我给你每一个小格这样一个编号，我要想获取编号为三的数据呢？我只要直接从编号三的小格子里面将数据取出来就行了，对不对？速度会非常的快，为什么呢？第一个这个编号是连续的，第二个这个编号是有范围的，对不对？但是啊，同学们，如果我要不知道我的索引下标怎么办，那么是不是就得从数组中的第一个开始，一个一个往后来查找呢？哎，这种方式呀，你就会发现它就没有之前我通过索引的方式去访问更快了，那么这种方式呢，我们称之为叫线性查找，也就是说它每一个都要找一遍，那么速度可就很慢了呀，那这怎么办呢？所以接下来呢，我们就给大家介绍一种方法，用于快速对已经排过序的数据进行查找，记住啊，我说的是排过序的数据，如果数据没有排序的话，那么就意味着没有规律可循，那你要想去查询的话就非常困难了啊，这个希望大家能够明白，我们现在要讲的这个方法的前提条件是数据是有序的，只是它在哪你不知道，但是数据是有序的。

说一下我们这里呢，把数据给大家准备一下来咱们拷贝。我们写上一个我们的三，我们点击OK啊，然后呢，把这个呢我们去掉，去掉以后呢，我们写上它，我们叫数据查询好，那首先呢，我先写上int中国号，写个numbers，我等于什么呢？咱们写上1234567好了，写完以后，那我现在就想从里面把我们的六取出来，那怎么做呢。我相信同学们一定会说啊，哎，这简单呀，我从数组的后面往前插两个，这不就行了吗？你看第一个第二个插两个不就取到了吗？那好，我问你，我假设从一到100的100个数中取这个六，它们也是有序的，怎么做呢？那你肯定又会说了，那我从前面取第六个不就行了吗？诶，大家想一想，为什么我们这一回就不从后面取了，刚才我就要从后面取呢？我们是七个数，你说我从后面取这个第二个，那我从一到一百一百个数的话，你说从我前面取取第六个就可以了。

哎，为什么呀，那是不是因为我们的六它离前面更近一些啊，所以我们大家想一想，在咱们查询数据的时候，我们其实啊，都会想要从一个离数据更近的地方开始查找，对吗？所以咱们接下来给大家介绍的这种数据的查询方式，也是基于这样的一个原理，就是我也知道谁离他更近一些，来咱们画图，咱们说明一下来。咱把这个数据呢，我们给大家准备一下，咱们准备一下来来来，我在这里呢，把这个呢，我们拷贝一下。嗯，往下吧。往下以后我放到这里啊，咱们放到放到这里，然后呢，我写上它，把这个写成一二啊，然后呢345，然后呢，我们放过来，然后呢，写上一个六，再写上一个七。

好了，我们再写上一个我们的漆啊，行，写上它行了，那颜色呢，给它稍微的我们变一变吧，都变成白色就可以了啊，然后呢，我们把这个呢复制，复制以后把这个给它包起来，这就好比一个数组的感觉就有了啊行了，那现在有了它以后，我说过了，我想把咱们当前的这个六给我取出来，这是我们现在查询的目标啊，但是我不知道它的位置呀，对吧，我不知道它的位置，我就想把六查出来，那怎么办呢？为什么我们说有的时候查询的比较慢呢？那不就是因为数据太多了吗？如果我们把这个数据变少的话，你的查询不就快了吗？所以啊，我们来复制一下干嘛呀，我把当前的这个数组呢，我一分为二啊，所以我给它来放到这，放到这以后，来我再复制一下，放到这边行了，放过来以后，我这个颜色呢，给它变成一个紫色，同学们想一想，我把当前的数组呢，我一分为二，哎，那这样的话，你就会发现我们的数据啊，它不是在我的左边就是在右边，但是呢，我们的数据是有序的呀，你就判断。

等一下你当前的数据比你中间的这个值是大还是小，不就完了吗？如果你比它大，那不用说了，肯定在右边，如果你比它小，肯定在左边，对不对？所以现在的重点就在于怎么办，你得确定一下我中间的这个值是多少，所以中间的这个值非常重要。I中间的这个字它是非常重要的，所以咱们写上它，咱们就叫M，对吧？我咪的这个字非常的重要啊，哎，老师啊，那如果我现在假设我找到了这个四的话，我要找的是这个六，这个六比我的四更大，那不用说了，肯定是在我们的右边吗？那左边你还看吗？左边你可就不看了，那你不看的话，我当前的数据大家想想，那是不是就变成了我们的567了呢？诶，我的数主量不就少了很多吗？对不对？我从五和七开始找数据不就更容易了吗？哎，老师，那这个该怎么找呢？这个跟刚才不是一样吗？我还是把咱们当前的这个数组呢，我一分为二，同学们看一下，我就从中间给我切分一下，就是从中间我从中间给我切分一下的话，那么我们当前的数组数据量不就少了吗？我们这咱们也这么做，可以这么做，也这么做了以后，那么就意味着我当前的这个它就变成了这个样子，来我复制，复制以后我放过来，放过来以后给它变成一个这个颜色，然后呢，给它放下去，那这样的话不就行了吗？

哎，巧了，同学们，我们中间的这个值恰恰就是你要的那个值吧，那么它的位置你不就知道了吗？所以同学们，这就意味着我当前就把这个六就查出来了，我问同学们，我查了几次呀？我是不是就查了两次呀，我先取他查了一次，然后呢，我再取它是不是又查一次，我只需要查两次就行了，但是如果呢，你要按照我们之前的这种方式，123456，诶你看你得查六次呀，对不对，同学们就是这样的，诶老师，那你要从后面查不太快了呢，我们这时候啊就没有办法了，为什么呢？我们只是比常规意义呀要快一些，你要是把特殊情况考虑进去，那就没法说了，为什么？因为大家想想，如果我要取的数正好是一呢，我要取的数是一的话，你循环一次不就出来了嘛，对不对？所以啊，我们不能拿特殊情况来考虑我的问题，我们拿到的是一种我们基本的一种解决方案，对吧，就这种方案一定比我们这种方案会更快，但是你说一定比极限情况还快吗？这个咱就不确定了。

啊同学们，那我当才我们的这个思路呢，我们再说一下，其实啊，我就是把我当前的整个数组呢，给我一分为二，找到中间值，找到中间值以后，我判断你要的值比这个值是大还是小，如果小在左边，如果大在右边对吧？然后呢，我把右边的这些值呢，给它拿出来，再取中间值，再比对谁大谁小在左在右，那么以此类推不就行了吗？所以你会发现我们当前有几个地方需要注意，第一个就是我中间的值，还有一个就是我的一个范围的变化，什么叫范围的变化呢？大家看一下我这边啊，本身我的start，我的start这个我们称之为叫起始位置，这个咱们称之为叫结束位置，对吧？好了，然后呢，我从中间呢，找了一个middle的值，那所以呢，我们的起始位置就有变化了，有什么变化呢？比方说我要的数据呢，比中间的那个值要大，所以我的结束位置是不会变的，但是我的起始位置它就发生变化对不对？哎，变化了，变成这了，变到这以后我再去什么呢？做判断，判断以后如果还是发现不对，那时候我的这个位置是不是又会发生变化呀，同学们能不能明白？

诶，老师啊，那什么时候就能找到我的值呢？很简单，要么你中间的这个值是你要的，要么我们的star和end它俩重合了，对不对，所以当我们的这个start和end它相等的时候，其实呀，我们就找到了我们想要的那个数据值了，对不对？哎，所以这种方式是可行的，我们每一回呢，都把我们当前的数组呢，给它一分为二，所以咱们这个查找的方式呢，有一个特定的称呼，叫折半查找法，也叫二分查找法，咱们叫二分查找法。

就是这样的啊，就是把我当前的数组啊，一分为二啊，然后呢，从我们两边去进行查找对不对，要么是左，要么是右，就是这么一个过程。好了，那这个我们该怎么实现呢？首先呢，我们这里呢，就先把我的查询目标啊，哎，查询我们的目标，哎，咱们写上咱们叫int，咱们叫target给number，它等于五，我就想把这个五给它查出来，看它在数组的什么地方，对吧？哎，好了，那然后呢，我要把那个范围给它界定好，我们的范围啊，我先写上一个start，它等于零，然后呢，我再写上一个end，它等于我们当前的numbers.lengths减一就是我索引的最后一个值，就是默认情况下我从头到尾，记住啊，同学们，默认情况下从头到尾就是我们要查询的范围。好了，那么接下来我们再去写上一个叫做middle中间的那个值，中间那个值我现在不知道是多少啊，所以我先给它个零啊，随便给它写一个，然后呢，我先加上一个叫well循环，诶，我为什么要well循环呢？是因为我们在整个的处理过程当中，我们的这个范围啊再发生变化对吧？什么时候找到了或者说不再查找了呢？就是当我的start和N这个范围重合的时候，或者简单来讲就是当我的start小于或等于N的时候，我们就应该去找，如果你的start比这个end都大了，那就没有意义了，对不对？所以我们的基本的循环条件就是我的范围的起点，它应该小于等于我们的终点，对吧？这是一个范围啊，对吧？你重合它也是一个值嘛，所以我这么写完了以后，接下来呢，我把中间的那个咪的值，我给它取出来。

诶，老师，这个middle的值应该怎么取出来，非常简单呀，你把这两个值相加，除二不就是中间的值嘛，对不对，范围的中间就是除二啊，所以我们这写上它，刚才我就写上啊，咱们叫middle，它等于我们的start，然后再加上我们的N，然后呢，给它除以二就行了，那这样的话我的中间值就有了，那好了，那接下来我就要判断一下了，你查询的目标它到底在中间值的左边还是右边，所以我就写上它了，咱们叫if，我们当前的numbers，我们写上一个叫middle，对吧，这就是我中间的那个值呀，你中间的这个值它如果大于了我们的它，给它诶拷贝拷贝以后来大于它，记住如果你大于它，说明你的数据应该在我的左边吧，为什么呢？因为我的中间值比你大嘛，那所以你应该在左边，你要在左边的话，那么这就意味着你的那个结束的范围，它应该什么，比我们中间的值应该减一，大家能不能明白，这就意味着当你在左边。

的话，你的end就应该变到了这个位置，它比middle值应该小一个一，没问题吧，同学们，这就是我们小的情况，那如果你要是我们大一的情况呢？所以else，我们的if，如果你当前我们的number，诶，我们拿过来，它如果要是小于我们当前的target number什么意思啊，就意味着你的咪的值啊，比你要的数呢要小，那么说明在我们右边啊，那么右边的话，我的起始位置不就应该发生变化吗？我的起始位置不应该放到这来了吗？所以他应该这么写，叫做start。

它应该叫做start，它等于我们middle值应该加一，你看这不就行了吗？那不对啊，还有一种情况啊，还有种什么情况呢？它相等的时候怎么办？如果中间的这个middle的值跟你当前要的值相同的话，就不用再循环了呀，直接跳出就完事了呀，我们直接break其实就可以了，同学们能不能明白老师说的意思，你这么写完其实就够了，所以我们这里写上一下。我们写上数据在我们数组的位置，然后呢位置，然后呢写上一个加号，我们就要middle就可以了，好了，写完了以后，同学们我们运行一下，看看结果运行运行以后你会发现我们当前的结果是我们的是。

01234没问题吧，哎，老师呀，我如果想查我们的四呢。对吧，我再运行，运行以后你看结果，你会发现结果应该就是三了吧，好，我们再来给他写成一个六，你给他一个六之后啊，我再运行一下，那不用说了，那结果肯定就是我们的五了嘛，你看这不就可以了吗？它的每一次的循环就会把数组呢分成一半，所以这种方式就叫二分查找法。这样的话效率上还是比较高的，要比咱们之前那个线性查找一个一个找要高不少啊。