0.参考

参考链接:二分查找的左闭右开和左闭右闭写法

1.思路

0. 序言

lower_bound查找的是升序序列中的第一个出现target的pos，区间应从右向左收缩。
upper_bound查找的是升序序列中的最后一个出现target的pos，区间应从左向右收缩。
主循环判断本质目的是为了确保整个区间能够被检索到。

1.左闭右开

• 每次循环的区间都是[left,right),在二分的时候，搜索区间去掉mid使得原始区间分为两块[left,mid),[mid+1,right),这样才能保证整个区间都被检索。
  所以left = mid + 1 和 right = mid

• 主循环判断条件：left< right,这和我们在其他循环中是一样的。
  比如 for (int i= 0; i< nums.size(); ++i)
  左闭右开的写法更常见，c++中迭代器返回的end就是右开的。
  在主循环跳出的时候，其实是[left,left),这个搜索空间为空，主循环确保了整个区间的检索。

1.1 lower_bound

实现lower_bound关键是target == nums[mid]的时候，我们仍然让right = mid，实现从右向左收缩.

int lower_bound(vector<int>& nums, int target){
    int left = 0, right = nums.size(), mid;
    while (left < right){
        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 (left >= nums.size() || nums[left] != target) return -1;
    return left;
}

upper_bound

• 实现 upper_bound关键是target = nums[mid]的时候，left = mid + 1 实现从左向右搜索。
• 最终推出循环返回的left是最后出现target的下一位，需要 left - 1 来正确返回下标