基础算法--整数二分

来自AcWing->活动->算法基础课

二分模板1

 1 int binary_search1(int l,int r){
 2     while(l<r){
 3         int mid=l+r+1>>1;
 4         if(check(mid)){
 5             l=mid;
 6         }else{
 7             r=mid-1;
 8         }
 9     }
10     return l;
11 }

二分模板2

 1 int binary_search2(int l,int r){
 2     while(l<r){
 3         int mid=l+r>>1;
 4         if(check(mid)){
 5             r=mid;
 6         }else{
 7             l=mid+1;
 8         }
 9     }
10     return l;
11 }

两个模板分别对应找绿边界和红边界

二分的本质就是对于某个性质，一半区间满足，一半不满足，然后更新区间，一定保证答案在更新之后的区间里

第一个模板向上取整的原因:

　　因为假设l=r-1，那么mid=l，而假设mid满足条件，那么就陷入了死循环中，向上取整的话，mid一开始就等于r