二分查找模版

对于一个递增序列我们要找大于等于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] 否则就是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
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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;
      else
       right=mid;
   }
   return l  //或者return r
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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;
       else
       r=mid;
   }
  return r;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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