[算法模板]二分

[算法模板]二分

两个不会翻车的二分板子：

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

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

注意，第二段代码mid计算需要加一，不然在(r-l=1)的时候会进入死循环。