二分查找的一般形态及左右逼近变式(LeetCode:34)

二分查找对于有序的数组是十分好用的查找方法，其使用分治法，将数组一分为二，每次排除一半的元素，复杂度是O(log(n))

一般形态：数组中没有重复元素

【更为详细的版本】

将数组分为

左边一坨 中间元素 右边一坨
0~mid-1   mid   mid+1~end

如果中间元素是目标，找到
如果中间元素小于目标，在右边一坨找
如果中间元素大于目标，在左边一坨找

vector<int> nums;
int l = 0;
int r = nums.size()-1;
while(l<=r)
{
	int mid = (l+r)/2;
	if(nums[mid]==target)
		return mid;
	else if(nums[mid]<target)
		l = mid+1;
	else
		r = mid-1;
}
return -1;

变式：查找第一个出现/最后一个出现的元素

如果数组中出现重复元素，并且要我们查找的是第一个出现/最后一个出现的值，那么必须使用二分搜索的变式

在找到目标元素的同时，不结束，而是根据我们的需要，进一步收缩搜索的范围，逼近边界的元素

比如我们想找第一个重复出现的目标元素，那么希望尽量的收缩右边界，此时我们令右边界=中间即可

if(nums[mid]==target)
	r = mid

同样，如果希望找到最后一个重复出现的目标元素，我们希望收缩左边界，令左边界=中间即可

if(nums[mid]==target)
	l = mid

注意

这么做的弊端是当区间元素个数小于三个时会卡循环，循环/递归结束的条件就是数组元素小于三个

对应的，我们对剩下的两个元素进行判断即可

• 如果希望找第一个重复出现的目标元素，那么依次判断区间左/右端点（结束时区间只有两个元素）
• 如果希望找到最后一个重复出现的目标元素，依次判断右/左端点即可

上述的后处理是必不可少的，因为区间被刻意的压缩，但是最后区间长度是2，不是1

题

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

这里其实可以直接 lower_bound upper_bound
【关于 lower_bound upper_bound】

也可以普通二分查找找到后向两边扩散

也可以找两次，下面的代码是两次逼近，（一次找最前一次找最后）的版本

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        int len = nums.size();
        vector<int> ans{-1, -1};
        if(len == 0) return ans;
        // 右边界收缩查找第一个重复元素
        int l = 0;
        int r = len-1;
        while((r-l+1)>2)
        {
            int mid = l+(r-l)/2;
            if(nums[mid]==target) 
                r = mid;
            else if(nums[mid]<target)
                l = mid+1;
            else 
                r = mid-1;
        }
        if(nums[l]==target) ans[0]=l;
        else if(nums[r]==target) ans[0]=r;
        else return ans;
        // 左边界收缩查找最后一个重复元素
        l = 0;
        r = len-1;
        while((r-l+1)>2)
        {
            int mid = l+(r-l)/2;
            if(nums[mid]==target)
                l = mid;
            else if(nums[mid]<target)
                l = mid+1;
            else
                r = mid-1;
            
        }
        if(nums[r]==target) ans[1]=r;
        else ans[1]=l;

        return ans;
    }
};

转载：https://blog.csdn.net/weixin_44176696/article/details/104412486