二分查找法 (Binary Search)

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

示例(Java)

递归逻辑

   public static <E extends Comparable<E>> int search(E[] data, E target){
        return search(data, 0, data.length - 1, target);
    }

    //递归
    private static  <E extends Comparable<E>> int search(E[] data, int l, int r, E target) {
        if( l > r) return  -1;
        int mid = l + (r - l)/2;
        if (data[mid].compareTo(target) > 0)
            return search(data, l, mid, target);
        if(data[mid].compareTo(target) < 0)
            return search(data, mid + 1, r, target);
        return mid;
    }

非递归逻辑

    public static <E extends Comparable<E>> int search2(E[] data, E target) {
        int l = 0, r = data.length - 1;
        while (l <= r) {
            int mid = l + (r - l)/2;
            if (data[mid].compareTo(target) == 0)
                return mid;
            if (data[mid].compareTo(target) < 0)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return -1;
    }

Binary Search

时间复杂度：

时间复杂度(不算排序)：O(logn)

相关变种问题

    // >target 的最小值的索引
    public static <E extends Comparable<E>> int upper(E[] data, E targt){
        // r = data.length 表示>target的值在数组最后一个元素的后面 数组中的所有元素都<target
        int l = 0, r = data.length;
        while (l< r) {
            int mid = l + (r- l)/2;
            if (data[mid].compareTo(targt) <= 0)
                l = mid + 1;
            else
                r = mid;
        }
        return l;
    }

    // > target, 返回最小索引
    // = target, 返回最大索引
    public static <E extends Comparable<E>> int upperCeil(E[] data, E targt){
        int u = upper(data,targt);
        if (u - 1 >= 0 && data[u - 1].compareTo(targt) == 0)
            return u - 1;
        return  u;
    }

    // >= target 的最小索引
    public static <E extends Comparable<E>> int lowerCeil(E[] data, E target){
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l)/2;
            if (data[mid].compareTo(target) < 0)
                l = mid + 1;
            else
                r = mid;
        }
        return l;
    }

    // <target 的最大值的索引
    public static <E extends Comparable<E>> int lower(E[] data, E target){
        int l = -1, r = data.length - 1;
        //当l与r相邻时 eg:0, 1 是 mid由于计算机下取整 mid = l + (r - l)/2 = 0, 所以l = 0 引起死循环。
        //解决办法： mid = l + (r - l + 1)/2 采用上取整
        while (l < r) {
            int mid = l + (r - l + 1)/2;
            if (data[mid].compareTo(target) >= 0)
                r = mid - 1;
            else
                l = mid;
        }
        return l;
    }

    // <= target 的最大索引
    public static <E extends Comparable<E>> int upperFloor(E[] data, E target){
        int l = -1, r = data.length - 1;
        //当l与r相邻时 eg:0, 1 是 mid由于计算机下取整 mid = l + (r - l)/2 = 0, 所以l = 0 引起死循环。
        //解决办法： mid = l + (r - l + 1)/2 采用上取整
        while (l < r) {
            int mid = l + (r - l + 1)/2;
            if (data[mid].compareTo(target) > 0)
                r = mid - 1;
            else
                l = mid;
        }
        return l;
    }

    // < target 的最大索引
    // = target 的最小索引
    public static <E extends Comparable<E>> int lowerFloor(E[] data, E target){
        int l = lower(data, target);
        if (l + 1 <  data.length && data[l + 1].compareTo(target) == 0)
            return l + 1;
        return  l;
    }