//左闭右开区间二分 [l,r) 
    //false false false false true true true  模型 不存在true返回 r 解空间尾下标+1
    ll l=0,r=n;
    while(l<r) {
        ll mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
        cout<<l<<endl;  //答案存在时 返回 l 不存在时返回n

//左闭右开区间二分 [l,r) 
    //true true true true false false false   模型 不存在true返回 l-1 解空间头下标-1
    ll l = 0, r = n ;

    while (l < r)
    {
        ll mid = ( l + r) >> 1;
        if (!check(mid)) r = mid;
        else l = mid + 1;
    }
    cout<<l-1<<endl; ////答案存在时 返回 l-1 不存在时返回-1

//闭区间二分 [l,r]
    //false false false false true true true  模型 不存在true返回 r 无法通过l判断是否存在答案
    ll l=0,r=n-1;
    while(l<r) {
        ll mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
        cout<<l<<endl;  //答案存在时 返回 l 不存在时返回n-1

//闭区间二分 [l,r] //此模型不受影响
    //true true true true false false false   模型 不存在true返回 l-1 解空间头下标-1
    ll l = 0, r = n-1 ;

    while (l < r)
    {
        ll mid = ( l + r) >> 1;
        if (!check(mid)) r = mid;
        else l = mid + 1;
    }
    cout<<l-1<<endl; ////答案存在时 返回 l-1

//开区间二分 (l,r)
    //false false false false true true true  模型 不存在true返回 r
    ll l=-1,r=n;
    while(l+1<r) {
        ll mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid;
    }
        cout<<r<<endl;  //答案存在时 返回 r 不存在时返回n

//开区间二分 (l,r) 
    //true true true true false false false   模型 不存在true返回 l
    ll l = -1, r = n;

    while(l+1<r)
    {
        ll mid = ( l + r) >> 1;
        if (!check(mid)) r = mid;
        else l = mid;
    }
    cout<<l<<endl; //答案存在时返回  l 不存在时返回-1

整数二分

可以归纳为两种模型:
对于check来说,可以把区间的取值情况分为:

flase flase flase flase true true true 和

true true true true flase false flase 两种模型

对于第一种情况,我们需要寻找的是第一个true(尽量在满足true的区间向左寻找答案)
对于第二种情况,我们需要寻找的是最后一个true(尽量在满足true的区间向右找答案)

在二分答案是经常出现两种类型: 最大值的最小值 和 最小值的最大值 分别可以对应于上面两种模型

int bsearch_1(int l, int r) //flase flase flase flase true true true (最大值的最小值)(向左找答案)(第一个)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch_2(int l, int r) //true true true true flase false flase (最小值的最大值)(向右找答案)(最后一个)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

stl 二分

upper_bound:

upper_bound(begin, end, value, cmp)
bool cmp(value, element)

upper_bound的第四个参数是自定义的匿名函数cmp，返回值为bool类型，cmp有两个参数，一个是value，对，你没看错，就是upper_bound的第3个参数value，另一个是element，也就是查找过程中与value比较的那个数。upper_bound返回的就是[begin, end)区间中第一个满足cmp(value, element)为true的数。下面看两个例子，注意看注释，方便理解。

lower_bound:

lower_bound(begin, end, value, cmp)
bool cmp(element, value)

注意，lower_bound的匿名函数element和value的顺序反过来了！lower_bound返回的是[begin, end)区间中第一个使cmp(element, value)为false的数。

从上面可以 看到 upper_bound 可以对应为 false false flase flase true true true 模型
lower_bound可以对应为 true true true true false false false 模型 只不过返回的是第一个false 我们返回时候-1即可

可以利用stl二分法序列中的答案

    // 二分答案 将序列答案进行抽象为 0 1 
    auto check=[](ll b)->bool {return b;};
    vector<ll> ve1={0,0,0,0,1,1,1};  
    ll k1=
    upper_bound(ve1.begin(),ve1.end(),bool{},[&](auto,auto b){return check(b);})-ve1.begin();
    // flase flase flase flase true true true 查找第一个true 查找不到返回 尾下标+1

    vector<ll> ve2={1,1,1,1,0,0,0};
    ll k2=
    upper_bound(ve2.begin(),ve2.end(),bool{},[&](auto,auto b){return !check(b);})-ve2.begin()-1;
    // true true true true false false false 查找最后一个true 查找不到返回 头下标-1

stl的二分只能在答案区间不太大的时候使用 因为序列需要空间 而手写二分是不需要额外序列的

我们可以用c20的惰性语法(【C20 下解二分答案的新思路 - 惰性的 views 和 ranges 算法】 https://www.bilibili.com/video/BV1c84y1L7bX/?share_source=copy_web&vd_source=9f32c5a7c3e06da2496e64725e429eea)来解决这个问题 而在python中可以直接使用库函数

对于python我们可以使用 bisect模块

bisect_left(L,True,key=check)
# 在L中查找x，x存在时返回x左侧的位置，x不存在返回应该插入的位置 (false,false,true,true)

bisect_right(L,True,key=check)-1  (check 里面需要对返回值取not)
在L中查找x，x存在时返回x右侧的位置，x不存在返回应该插入的位置 (true,true,false,false)

实数二分