博客

普通二分查找比较简单，应用于查找某值是否存在于数组中；

但是普通二分查找也有缺点，就是当有多个target值存在，想要返回target左右边界的下标时，普通二分查找就没有办法完成，虽然说可以在查找到某一坐标后向左向右分别线性查找，但这时候就没有办法保证时间复杂度了，这时候就可以利用带边界的二分查找算法。

以下代码的搜索区间均为左闭右开，即left = 0, right = nums.size()；如果是左右均是闭区间即right = nums.size()-1；时是有略微的不同不要盲目地套模板，要注意边界细节。

左边界二分查找：

// 寻找左边界
// 左闭右开
int binSearchLeftBound(vector<int> nums, int target){
    int left = 0, right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            right = mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else if(nums[mid] > target){
            right = mid;
        }
    }
    if(nums[left] == target) return left;
    return -1;
}

右边界二分查找：

// 寻找右边界
// 左闭右开
int binSearchRightBound2(vector<int> nums, int target){
    int left = 0, right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            left = mid + 1;
        }else if(nums[mid] > target){
            right = mid;
        }else if(nums[mid] < target){
            left = mid + 1;
        }
    }
    if(nums[left-1] == target) return left-1;
    return -1;
}