关于二分

1. 第一种二分查找

• 1)lower_bound函数,查找相同区间的第一个数的下标

int lower_bound(vector<int>& nums,int target)
{
	int l=0,r=nums.size()-1,mid;
	while(l<=r)//区间不为空
	{
		mid=l+(r-l)/2;//防止溢出
		if(nums[mid]<target)l=mid+1;//[mid+1, right],把小于目标的数字全部排除
		if(nums[mid]>=target)r=mid-1;//[left, mid-1],首先大于目标的数字全部排除
		//因为第二个if能够判断等于,又因为循环结束的标志为区间为空
		//所以right的位置结束的地方的数字一定小于target
		//所以结束的时候为r<l,即l的位置即为连续相同区间的第一个位置
	}
	return left;
}

• 2)upper_bound函数查找相同区间的末尾的下标

int upper_bound(vector<int>& nums,int target)
{
	return lower_bound(nums, target+1)-1;
	//没错,利用上一个的基础二分去查找值target+1的数
	//尽管没有找到,返回的下标也是相同区间的下一位,此时pos-1就是区间结束的位置.
}

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

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