二分查找

适用于在「有序」的数据中快速的找到目标值。

时间复杂度：$O(nlogn)$

// 找到大于等于目标数的第一个位置
public int lower_bound(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while(low < high){
        int mid = (high - low) / 2 + low;
        if (nums[mid] < target) { 
            low = mid + 1; 
        } else {
            high = mid;
        }
    }
    return low;
}

// 找到大于目标数的第一个位置
public static int upper_bound(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = (high - low) / 2 + low;
        // System.out.println(mid);
        if (nums[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}