二分查詢算法

二分查找（binary search），也稱折半搜索，是一種在有序數(shù)組中查找某一特定元素的搜索算法。

時間復雜度:折半搜索每次把搜索區(qū)域減少一半，時間復雜度為O(log n)。
空間復雜度: O(1)。

// 遞歸實現(xiàn)
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);
    }
}
// 循環(huán)實現(xiàn)
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、若在數(shù)組中找到值，則返回該值得下標
    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;
    // 初始化數(shù)組
    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;
}

馬戲團人塔