二分查找的两个模板

1. 循环必须是l < r
2. check() 判断是否符合条件
3. 如果 出现 r = mid - 1, 则前面求mid 需要 加1
4. 出循环一定是 l == r , 所以结果使用那个都行

找出 >= 给定数的第一个位置(满足条件的第一个数)

public static int binSearch(int[] num, int l, int r) {
    while(l < r) {
        int mid = l + r >> 1;
        if(check()) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
}

找出 <= 给定数的最后一个数 (满足某个条件的最后一个数)

public static int binSearch(int[] num, int l, int r) {
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(check()) {
            r = mid - 1;
        } else {
            l = mid;
        }
    }
}