基本思想

二分查找，单调性不是必须的

想象一个无限长的数组，左边全是false，右边全是true，

存在第一个使得f(x)=true的x=k，也就是突变点，突变点之后均满足f(x)=true

给定一个包含突变点的左闭右开坐标范围[l,r)，二分查找可以不断缩小范围找出这个点，最后l和r重叠于突变点k

模板如下，f(x)可以套用任何条件，只要问题可以抽象成上面描述的性质即可

int binarySearch(vector<int>& nums) {
    int n = nums.size();
    int l = 0, r = n;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (f(m)) r = m;
        else l = m + 1;
    }
    return nums[r];
}

二分过程中，中点如果满足f(m)=true，说明突变点只会是m或m的左侧，缩小右边界r=m即可，否则缩小左边界，l=m+1

整个过程不断把右边界缩小到第一个满足f(x)=true的下标；若右边界已到位r=k，而左边界未重合，则之后只会一直缩小左边界，（因为中位数是下中位数，不会出现中位数是k），直到l=r=k

升序数组找到一个大于等于target的下标

对于升序nums，存在一个最小下标x，在该下标及其之后满足f(x)=true

那么f(x) = (nums[x] >= target)，代入模板得

int binarySearch(vector<int>& nums, int target) {
    int n = nums.size();
    int l = 0, r = n;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (nums[m] >= target) r = m;
        else l = m + 1;
    }
    return nums[r];
}

而传统的二分查找指定target的下标，只是把上面的条件取等时单独考虑，直接返回而已，是特殊情况

对应的C++库函数实现了相同功能

lower_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp)

该函数描述如下

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

The elements are compared using operator< or comp.

The elements in the range shall already be sorted according to this same criterion (operator< or comp), or at least partitioned with respect to val.

在具体实现上有细微区别，大体如下，与上面的实现相比，if的条件和两个分支顺序相反

因为C++该函数使用comp，语义是小于，而lower_bound目标是第一个不小于，也就是第一个大于等于，所以comp(nums[m], target)这里相当于!f(条件)

（如果需要自定义comp函数以使用lower_bound找到第一个满足xx条件的元素，就需要注意条件和comp的关系，有时候需要取反）

int binarySearch(vector<int>& nums, int target) {
    int n = nums.size();
    int l = 0, r = n;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (comp(nums[m], target)) l = m + 1;
        else r = m;
    }
    return nums[r];
}

升序数组找到一个大于target的下标

对于升序nums，存在一个最小下标x，在该下标及其之后满足f(x)=true

那么f(x) = (nums[x] > target)，代入模板得

int binarySearch(vector<int>& nums, int target) {
    int n = nums.size();
    int l = 0, r = n;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (nums[m] > target) r = m;
        else l = m + 1;
    }
    return nums[r];
}

对应的C++库函数实现了相同功能

upper_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp)

该函数描述如下

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

The elements are compared using operator< or comp.

The elements in the range shall already be sorted according to this same criterion (operator< or comp), or at least partitioned with respect to val.

具体实现大体如下，if的条件和分支顺序和上面是一致的，

因为语义上comp是小于，而upper_bound目标是第一个大于，

所以这里comp(target, nums[m])就是f(条件)

（注意这里comp两个参数传入的位置是和lower_bound的comp相反的）

int binarySearch(vector<int>& nums, int target) {
    int n = nums.size();
    int l = 0, r = n;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (comp(target, nums[m])) l = m + 1;
        else r = m;
    }
    return nums[r];
}