二分查找算法

一，应用场景：有一个有序数组，想从里边找到某一个元素的位置

二，有序且元素唯一的实现

1.基础版

    public static int binary1(int[] a, int target) {
        int i = 0;
        int j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
 
        }
        return -1;
    }

2.平衡版

    public static int binary2(int[] a, int target) {
        int i = 0;
        int j = a.length ;
        while (1
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;
            }else {
                i= m;
            }
 
        }
        if (a[i]==target){
            return i;
        }
        return -1;
    }

来说一下上边两种方案的区别：其实基础版已经可以解决大部分场景的问题了，那为什么出现平衡版呢，主要是当数组数据规模很大时候，减少了每次循环判断的条件，只在循环中去缩小范围，不去做具体的取值判断，因为我们知道如果数据规模很大，那么取中间索引刚好落在目标的可能就很小，所以我们干脆将这个权利剥夺掉，当范围缩小到最后时再去判断

我们索引取中为什么采用>>>：为什么不用/2呢，假如数据数据量超过了整数可以表示的最大范围，那么i+1很有可能就会超过整数最大值，就会变为负数，因为java中不存在无符号整数，二进制最高位代表的是符号位，那这样的话负数/2肯定还是负数，因为这样操作不会改变最高位，如果我们使用>>>1可以达到同样效果的同时还防止了当超过范围变为负数后/2为负数的场景