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

  • 查找 第一个大于/大于等于 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;
}