二分查找 | Joker With Time Passing!

¶二分查找

¶概念解释：

二分查找也叫做折半查找，是一种在有序数据序列中进行指定数据位置查找的算法，方式是每次取数据序列的中间值和将要查找的值进行对比，因为数据有序，所以要么这个中间值大于目标值，可以继续以同样的方法向右查找；小于目标值则同理向左查找，直到找到目标值的位置或者数据不存在。
光从思路来看有分治法的影子：对于每一段数据范围的查找思路都是相同的，取中间值判断，然后决定下一次搜索的数据范围，再以同样的方法判断。
从效率的角度上来说，对于一个 n 长的数组，要查找指定值的位置，可以顺序从头至尾遍历，这样操作的时间复杂度就是O(n)；而二分查找则每次都将查找范围缩小一半，从 n 到 n/2 ，n/4,n/8…n/2^k ，效率提升十分明显

¶算法实现

实现有递归和非递归两种，非递归的实现基于循环，其实之前学到递归的时候也讲过，所有的递归代码都可以转化成循环来实现

循环版本:

public static int binarySearch(int[] a, int target) {

    /**
         * 拆解一下二分查找的思路：
         * 1.先确定数组中点位置，取中间值进行比较
         * 2.如果不匹配，更改数组比较的范围再次匹配
         * 3.直到找到对应的元素下标或查找范围缩小至0
         */
    int index = -1;
    int n = a.length;
    int low =0;
    int high = n-1;
    int mid = low + ((high-low)>>1);

    while(low<high){
        int value = a[mid];
        if(target == value){
            return mid;
        }else if(target < value){
            //去前半段查找
            high = mid-1;
            mid = low + ((high-low)>>1);
        }else{
            //去右半段查找
            low = mid+1;
            mid = low + ((high-low)>>1);
        }
    }
    return index;
}

以返回值-1代表当前数组不存在目标值，否则就会返回目标值的下标
low 和 high的更新根据大于还是小于目标值，决定 mid-1 还是 mid+1
循环代码的退出条件是当数组已经遍历完成时，如果还没有匹配到目标值，则说明目标值不存在
最开始更新 mid 的方法是 : (n-1)/2，毫无疑问地错了，当再次计算 mid 位置的时候就无法得出正确位置了；正确确定mid的位置应该是 low + (high-low)/2 ，取要查找区间的中点加上低位，这里优化成了位运算

递归版本：


public static int binarySearchRecursive(int a[],int low,int high,int target){

    //先明确退出条件
    if(low>=high){
        return -1;
    }
    int mid = low + ((high-low)>>1);
    int value = a[mid];
    if(value == target){
        return mid;
    }else if(value > target){
        high = mid-1;
        return binarySearchRecursive(a,low,high,target);
    }else{
        low=mid+1;
        return  binarySearchRecursive(a,low,high,target);
    }
}

写递归版本的时候出了个乌龙：没有将后面的递归return，导致查找到指定位置之后，将值向上传递了，结果返回-1
判断的思路和循环是一样的，递归代码比循环看起来简洁很多

¶思考题：

求一个数的平方根，精确到小数点6位
思路:
1. //TODO

¶二分变体

上面实现的二分查找是最简单的二分查找，因为它是基于数组没有重复元素的前提进行的，而是实际上二分的应用会比这复杂。下面有四个二分查找的变体：

变体一:查找第一个值等于给定值的元素 ：如果将之前的数组稍微改变，对一部分数据增加重复值，即使数组依旧有序，根据二分缩小范围的方式，是无法确保能查找第一个指定元素位置的
实现:


public static int binaryFirstIndex(int[] a,int target){

    /**
         * 重新拆解一下二分的思路:
         * 1.仍然使用折半的方式进行查找
         * 2.当定位到一个符合目标值元素的时候，也就是 a[mid] = target
         * 3.考虑再次向前二分查找？low ~ mid 位置，如果仍有匹配数据，更新index;
         * 4.直到遍历完成 low ~ mid 区域
         */

    int index = -1;
    int n = a.length;
    int low = 0;
    int high = n-1;
    int mid = low + ((high-low)>>2);
	//注意，这里退出循环的条件变了，因为存在重复元素
    while (low <= high) {
        int value = a[mid];
        if (target == value) {
            //这里匹配到了目标值,先记录下来
            index = mid;
            //尝试往 low ~ mid-1 的区域进行二分,不用向后查找
            high = mid-1;
            mid = low + ((high - low) >> 1);
        } else if (target < value) {
            //去前半段查找
            high = mid - 1;
            mid = low + ((high - low) >> 1);
        } else {
            //去右半段查找
            low = mid + 1;
            mid = low + ((high - low) >> 1);
        }
    }

    return index;
}

实现起来比较简单，就是在第一次匹配到目标值之后，向前去查找是否有下标小于当前下标的值，有则更新位置
和之前的区别还有一点就是：退出循环的条件变了，只有当low>high 而不是 low >= high 时才会退出循环；因为在第一次定位到 target 位置之后，low的位置没有再变化过，如果恰好从 low ~ mid 位置的元素值都是 target ，会因为 low == high 而提前退出循环，输出 index = low + 1；这显然是不对的

变体二 :查找第一个大于等于目标值的元素位置 : 其实思路和之前是类似的，只是匹配条件改变了；而且第一个变体的实现还有可以优化的地方，尝试在这里实现一下；

思路：

查找到第一个 >=target 的元素位置，有没有其他方式确定这个是第一个 >= target 的元素？或者说其他判断终止查询的条件是什么？
当 a[mid] >= target && mid !=0 && a[mid-1] < target 时，也能够说明 mid 是我们要查找的位置


public static int binaryFirstMoreThanIndex(int[] a, int target) {


    /**
         *  当 mid ==0  || (mid !=0 && a[mid-1]<target) 时循环退出
         */
    int index = -1;
    int n = a.length;
    int low = 0;
    int high = n - 1;
    int mid = low + ((high - low) >> 2);
    while (low <= high) {
        int value = a[mid];
        if (value < target) {
            low = mid +1;
            mid = low + ((high - low) >> 1);
        } else if (value >= target) {
            //这里变更了退出循环的条件
            if (mid == 0 || (mid != 0 && a[mid - 1] < target)) {
                return mid;
            }
            high = mid - 1;
            mid = low + ((high - low) >> 1);
        }
    }
    return index;
}

其实实现了第一个就能实现第二个，思路是一样的，都是在定位第一个目标位置之后，决定是否还需要在指定区间继续进行查找
剩下两个变体是查找最后一个值等于以及最后一个值小于等于目标值，这里就不再写多余的代码了。

¶小结：

二分查找适合在数据量适中的有序数组中进行指定值的定位，用来查找的数据结构要能够支持随机访问；
这里举的例子都是数组，但是其实当需要创建一个很大的数组时，意味着需要一块很大的连续内存空间，存储数据本身已经是意见很费力的事情了，此时是不适合使用二分查找的
以上几种二分的实现在实际场景中的应用不怎么多，偏理论

¶问题: 在循环有序数组中实现二分查找

先确定循环有序数组的定义:
1. 将一条有序数组从某一个分界点断开，将较小的一段拼接到分界点之后，例如 {5,6,7,8,1,2,3,4}
2. 从分界点分开，两端各自都是有序的

思路：

先找到循环有序数组的分界点：**当 i != 0 && i != n-1 时，存在 a[i] > a[i+1] ，i 就是分界点 **
确定查找区间：在找到分界点的情况下，查找 target 可以分为三种情况 : a[0] ~ a[i] , a[i+1] ~ a[n-1] ,a[i] 在前两个区间可以通过二分查找定位到元素位置
实现：这个版本的实现相当粗糙，执行效率也低，需要优化


public static int binarySearchInCycleArray(int[] a, int target) {

    int n = a.length;
    int index = -1;
    int low = 0;
    int high = n - 1;
    int mid = low + ((high - low) >> 1);

    for (int i = 0; i < n; i++) {

        if (i != 0 && i != n - 1) {
            if (a[i] > a[i + 1]) {
                // 找到了分区点
                index = i;
                //和a[n-1] 比较确定最后应该查找的区间
                if (a[i] > target) {
                    if (a[n - 1] > target) {
                        //在 a[i+1] ~ a[n-1] 之间二分查找
                        low = i + 1;
                        high = n - 1;
                        mid = low + ((high - low) >> 1);
                        while (low < high) {
                            if (a[mid] == target) {
                                return mid;
                            } else if (a[mid] > target) {
                                high = mid - 1;
                                mid = low + ((high - low) >> 1);
                            } else {
                                low = mid + 1;
                                mid = low + ((high - low) >> 1);
                            }
                        }
                    } else if(a[n-1] < target){
                        //在 a[0] ~ a[i] 之间使用二分查找
                        high = i-1;
                        mid = low + ((high - low) >> 1);
                        while (low < high) {
                            if (a[mid] == target) {
                                return mid;
                            } else if (a[mid] > target) {
                                high = mid - 1;
                                mid = low + ((high - low) >> 1);
                            } else {
                                low = mid + 1;
                                mid = low + ((high - low) >> 1);
                            }
                        }
                    }else{
                        return n-1;
                    }
                }else{
                    return -1;
                }
            }
        }else{
            if(a[i]==target){
                return target;
            }
        }

    }
    return index;
}

在各自分区的二分查找应该有问题，因为这里还需要额外处理两端的情况
可以将实现过程拆分成两部分：先查找分区点，再使用二分定位
实现优化 ：


public static int binarySearchInCycleArray(int[] a, int target) {

    int n = a.length;
    int index = -1;
    for (int i = 0; i < n; i++) {
        if (i != 0 && i != n - 1) {
            if (a[i] > a[i + 1]) {
                // 找到了分区点
                index = i;
                break;
            }
        }
    }
    if (a[index] == target) {
        return index;
    } else if (a[index] > target) {
        if (a[n - 1] > target) {
            return binarySearchRecursive(a, index + 1, n, target);
        } else if (a[n - 1] < target) {
            return binarySearchRecursive(a, 0, index, target);
        } else {
            return n - 1;
        }
    } else {
        return -1;
    }
}

将内部的循环改成了二分查找的递归版本，需要注意high的取值，会影响到在边界查找的情况

¶二分查找

¶概念解释：

¶算法实现

¶思考题 ：

¶二分变体

¶小结：

¶问题: 在循环有序数组中实现二分查找

¶思考题：