!!!二分模板
如何写一个二分
- 标准格式
int l,r;
//找第一个大于等于x的位置,所求答案为l(等价于r+1)
while(l<=r){
int mid=(l+r)>>2;
if(a[mid]>=x)r=mid-1;
else l=mid+1;
}
//找第一个小于等于x的位置,所求答案为r(等价于l-1)
while(l<=r){
int mid=(l+r)>>2;
if(a[mid]<=x)l=mid+1;
else r=mid-1;
}
解释
第一段
- 对于每一次进入if:mid指向的都是大于等于x的元素,更新x为小于mid指向元素的第一个元素,无论如何,在l超过r之前(即结束循环前),总会到最后一次遍历使得r指向第一个小于x的数或者x,若指向的是x,则在下一次l会更新至等于r,最终使得l/r-1为x
- 简单来讲就是,该循环总能使得r指向的是第一个小于x的位置,l指向第一个不小于x的位置
第二段
- 同理于第一段,循环总使得l指向第一个大于x的位置,r指向第一个不大于等于x的位置
如何区分
- 其实归根结底就是思考到底是找大于等于还是小于等于,然后把找的东西放进if条件,把剩下的那个作为答案