二分查找寻找左右边界

讨论几个二分查找的变换问题，主要分为两类：

• 查找 第一个大于/大于等于 target 的数(左边界)

• 查找 最后一个小于/小于等于 target的数(右边界).

重点是注意临界条件，小心会死循环。本文假设数组为单调递增。

左边界

• 查找第一个大于 target 的数

// >
int binSearchUpper(vector<int> &array, int target){
    int left = 0, right = array.size() - 1;
    while(left < right){
        int mid = left + (right - left) /2;
        if (array[mid] > target)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}

• 查找第一个大于等于 target 的数

// >=
int binSearchUpperEq(vector<int> &array, int target){
    int left = 0, right = array.size() - 1;
    while(left < right){
        int mid = left + (right - left) /2;
        if (array[mid] >= target)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}

右边界

• 查找最后一个小于 target 的数

// <
int binSearchLow(vector<int> &array, int target){
    int left = 0, right = array.size() - 1;
    while(left < right){
        //注意这里需要 +1，否则会死循环
        int mid = left + (right - left + 1) /2;
        if (array[mid] < target)
            left = mid;
        else
            right = mid - 1;
    }
    return left;
}

• 查找最后一个小于等于 target 的数

// <=
int binSearchLowEq(vector<int> &array, int target){
    int left = 0, right = array.size() - 1;
    while(left < right){
        //注意这里需要 +1，否则会死循环
        int mid = left + (right - left + 1) /2;
        if (array[mid] <= target)
            left = mid;
        else
            right = mid - 1;
    }
    return left;
}