二分查找模版-Toy模板网

这篇具有很好参考价值的文章主要介绍了二分查找模版。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

对于一个递增序列我们要找大于等于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;
      else
       right=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;
       else
       r=mid;
   }
  return r;
}

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

到了这里，关于二分查找模版的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！