二分查找与边界二分查找（寻找边界）_二分查找边界

一、普通二分查找

场景描述

普通二分查找只用查找到目标值即可，假定目标只有一个，或者多个目标值只用寻找到一个

过程：

1、设置边界为left<=right

2、设置mid为left和right的中间位置，可任意上下取整

3、若目前的mid大于target，更新right，以缩小查找范围

4、反之目前的mid小于target，更新left，以缩小查找范围

5、若此刻mid刚好等于target，返回mid的下标即可

6，反之，当left>right也没有找到target表示容器内没有target

顺利找到图解：

找不到图解：

二、边界查找 

场景描述：

存在多个target，需要找到target开始位置与结束位置，belike：

过程：

1、分别找左边界和右边界

左边界：

1、将mid向下取整

2、寻找右边界，若当前mid大于或者等于target，更新right=mid

3、若当前mid小于target，更新left=mid+1

4、循环的条件是left<right，即当left==right时，left和right同时指向左边界跳出循环。

右边界：

1、将mid向上取整

2、寻找左边界，若当前mid小于或者等于target，更新left=mid

3、若当前mid大于target，更新right=mid-1

4、循环的条件是left<right，即当left==right时，left和right同时指向右边界跳出循环。

注意细节！！！

1、这里为什么不是更新right=mid-1呢？

答：因为如果当前mid刚好是左边界，如果right=mid-1的话，使得left和right所查找的范围内根本没有target，自然找不到边界值啦

2、为什么左边界需要向上取整右边界需要向下取整呢？

答：图解：

示例题目：力扣：在排序数组中查找元素的第一个和最后一个位置

大家可以试着做一做，答案给大家附上

题目代码：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if (nums.empty()) return { -1,-1 };//为空时的情况
        int l = 0, r = n - 1;//初始化并查找左端点
        while (l < r)
        {
            int mid = (l + r) / 2;//向前取mid
            if (nums[mid] >= target) r = mid;//找到最左边的端点
            else l = mid + 1;
        }
        if(nums[r]!=target) return { -1,-1 };//若一个target都没有找到
        int temp = r;//temp暂存左端点的值
        l = 0; r = n - 1;//初始化并查找右端点
        while (l < r)
        {
            int mid = (l + r + 1) / 2;//向后取mid
            if (nums[mid]<=target) l = mid;//找到最右边的端点
            else r = mid -1;
        }
        return { temp,r };
    }
};