浅谈二分的细节问题

标签:while   class   条件   细节问题   str   else   inline   最小值   lse   

最大值最小

给定一个不降的序列 \(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\)

最小值最大

浅谈二分的细节问题

标签:while   class   条件   细节问题   str   else   inline   最小值   lse   

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

版权声明:完美者 发表于 2020-10-31 1:33:54。
转载请注明:浅谈二分的细节问题 | 完美导航

暂无评论

暂无评论...