关于二分

回复帖子

@尘曦的诺言 2020-03-27 08:32 回复

众所周知,二分的策略对于不同问题有略微不同的边界条件或修改策略。那么为了偷懒,不动脑子下面这种做法是否可以处理所有的边界问题?(以二分答案,使答案最大值最小为例)

while(l+5<r)
{
   int mid = (l + r) >> 1;
   if(check(mid)) r = mid;
   else l = mid;
}
for(int i = l;i <= r;++i)
   if(check(i))
   {
      ans = i;
      break;
   }
@suxxsfe  2020-03-27 09:03 回复 举报

@尘曦的诺言
这样单独记一个ans,然后用l<=r就没错过

while(l<=r)
{
   int mid = (l + r) >> 1;
   if(check(mid)) r = mid-1,ans=mid;
   else l = mid+1;
}
return ans;
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。