整数二分

二分不一定要单调性，但有单调性必定可以二分,所以二分的本质并不是单调性

定义一种性质(例如大于x,小于x,max,min…)，一个区间内，右半边是满足这个性质的，左半边是不满足这个性质的

而二分就是在寻找这两个部分的边界

模板1：（边界1）

1.中间值: mid=(l+r+1)/2

2.如果mid符合区间1性质的话，那么答案在mid~r之间，更新方式为l=mid

如果mid不符合区间1性质的话，那么答案在l~mid-1之间，更新方式为r=mid-1

//区间[l,r]被划分为[;,mid-1]和[mid,r]时使用
int bsearch_1(int l,int r)
{
    while(l<r)
    {
        int mid=(l+r+1)>>1; 
        //不加1的话会死循环
        //相当于/2，但是>>是向下取整,/2是向0取整
        if (check(mid)) l=mid;
        else r=mid+1;
    }
    return l;
}

模板2：（边界2）

1.中间值：mid=(l+r)/2

2.如果mid符合区间2的性质的话，那么答案在l~mid之间，更新方式为r=mid

3.如果mid不符合区间2的性质的话，那么答案在mid+1~r之间,更新方式为l=mid+1

//区间[l,r]划分为[l,mid]和[mid+1,r]时使用
int bsearch(int l,int r)
{
    while(l<r)
    {
        int mid=(l+r)>>1;
        //相当于/2，但是>>是向下取整,/2是向0取整
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    return l;
}