二分查找

二分查询算法

二分查找（binary search），也称折半搜索，是一种在有序数组中查找某一特定元素的搜索算法。

时间复杂度:折半搜索每次把搜索区域减少一半，时间复杂度为O(log n)。
空间复杂度: O(1)。

// 递归实现
private int binarysearch(int[] array, int low, int hight, int target) {
    if (low > hight) {
        return -1;
    }
    int mid = low + (hight - low) / 2;
    if (target == array[mid]) {
        return mid;
    } else if (target > array[mid]) {
        return binarysearch(array, mid + 1, hight, target);
    } else {
        return binarysearch(array, low, mid - 1, target);
    }
}
// 循环实现
public int binarysearch(int[] array, int target) {
    int low = 0;
    int hight = array.length - 1;
    while (low >= hight) {
        int mid = low + (hight - low) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (target > array[mid]) {
            low = mid + 1;
        } else {
            hight = mid - 1;
        }
    }
    return -1;
}
// Arrays.binarySearch使用
    1、若在数组中找到值，则返回该值得下标
    2、若没有找到，则返回值为负的插入点值（从1开始）
public int bestSeqAtIndex2(int[] height, int[] weight) {
    int len = height.length;
    int[][] arrs = new int[len][2];
    for (int i = 0; i < len; i++) {
        arrs[i][0] = height[i];
        arrs[i][1] = weight[i];
    }
    // 按照身高排序(升) 升高相同按照体重排序(降)
    Arrays.sort(arrs, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
    // 求体重最长递增子序列
    // 初始化长度
    int res = 0;
    // 初始化数组
    int[] dp = new int[len];
    for (int[] arr : arrs) {
        int i = Arrays.binarySearch(dp, 0, res, arr[1]);
        if (i < 0) {
            // 该值应该放入的位置
            i = -(i + 1);
        }
        dp[i] = arr[1];
        // 维护最长递增子序列的长度
        if (i == res) {
            res++;
        }
    }
    return res;
}

马戏团人塔