首页 > 其他 > 详细

浅谈二分的细节问题

时间:2020-10-27 20:36:35      阅读:34      评论:0      收藏:0      [点我收藏+]

最大值最小

给定一个不降的序列 \(a\),求其中大于等于 \(x\) 的第一个数。

其实就是查找第一个合法的点。

while(l<r)
{
      mid=(l+r)>>1;
      if(a[mid]<x)l=mid+1;
      else r=mid;
}

如果当前 \(mid\) 小了,就向右寻找,当前 \(mid\) 不可能是答案,可以直接忽略 \(mid\),以 \(mid+1\) 为左端点。

如果当前 \(mid\) 大了或等于了,就向左寻找,当前 \(mid\) 可能是答案,不可以直接忽略 \(mid\),应该以 \(mid\) 为右端点。

初始条件默认 \(l\leq r\)。因为是整除 \(\boldsymbol 2\),所以在循环中 \(mid\in\left[l,r\right),mid+1\in\left[l,r\right]\)

考虑死循环的情况,\(l\) 这里有 \(+1\) 肯定是不会的,而 \(r=mid\) 显然是不可能的。

所以最后 \(l=r\)

最小值最大

浅谈二分的细节问题

原文:https://www.cnblogs.com/May-2nd/p/13886594.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!