网站 开发美食网站首页模板

对于一个递增序列我们要找大于等于target的数，返回结果的下标时
比如 序列 5 7 7 8 8 10
初始化左右指针l=0 r=n-1 猜测区间 [l,r] 闭区间，mid=(l+r)/2 防溢出就写成 mid=l+(r-l)/2
如果有nums[mid]<target 那么[l,mid]这个区间的数就都小于target 更新 l=mid+1;
否则就是nums[mid]>=target [mid,r]这个区间的数都大于等于target 更新r=mid-1;
终止时返回l,拿这个案例序列走一遍找8，最后l和r都指向下标3处的8,此时,l=3,r=3,mid=3 然后更新r=mid-1=2 l>r 跳出循环 结果就是l或 r+1 返回3，再比如找3，会发现r不断更新r=1,-1 跳出循环
返回l=0, 当找大于10的数时，l不断更新r不动了最后跳出循环就是返回数组的长度

int lower_bound1(vector<int>&nums,int target)
{int l=0,r=nums.size()-1;  //闭区间[l,r]while(l<=r){int mid=l+(r-l)/2；   //防溢出if(nums[mid]<target)l=mid+1;else r=mid-1;}return l;     //最后跳出循环 l>r    结果是r+1 或者l 因为 此时r+1=l
}

int lower_bound2(vector<int>&nums,int target)
{int l=0,r=nums.size();    // 左闭右开  [l,r)while(l<r){int mid=l+(r-l)/2;if(nums[mid]<target)l=mid+1;elseright=mid;}return l  //或者return r
}

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

上述我们讨论了 在序列中找 >=target 的计算方法 ，对于>target <target <=target 这里都可以从第一种情况来转换：
我们要找大于target的数，就可以使用上面的lower_bound 找 >=target+1
我们要找小于target的数 就可以使用上面的lower_bound招到>=target 的数左边的那个数，也就是返回的下标再减一
我们找小于等于target的数 就可以使用前面大于target返回的结果减一