在单调递增序列 a 中查询 x 的后继
- while(l<r){
- int mid=(l+r)>>1;
- if(a[mid]>=x)
- r=mid;
- else l=mid+1;
- }
- return a[l];
在单调递增序列 a 中查询 x 的前驱
while(l<r){ int mid=(l+r+1)>>1; if(a[mid]<=x) l=mid; else r=mid-1; } return a[l];
若是单调递减序列 那么将 if 和 else 后面的语句交换一下位置就好了
注意, 对于两种不同的目的, 与之对应的 mid 是不同的, 不然有可能会造成边界错误, 然后就是死循环, 这也是二分容易写挂的原因.
来源: http://www.bubuko.com/infodetail-3236113.html