整数二分的基本步骤:
1.找一个区间[L,R],使得答案一定在区间中。
2.找一个判断条件,使得判断条件具有二段性,并且答案一定是该二段性的分界点。
3.分析中点mid在该判断条件下是否成立,如果成立,考虑在哪个区间;如果不成立,考虑在哪个区间。
4.如果更新方式是R=mid, 不做任何处理;如果更新方式是L=mid+1,则需要在记算mid时+1。
//第一种模板
while(l<r){
int mid=l+r+1 >> 1;
if(check(mid)){
l=mid;
}else {
r=mid-1;
}
}
//第二种模板
while(l<r){
int mid=l+r >>1 ;
if(check(mid)){
r=mid;
}else {
l=mid+1;
}
}