二分答案的实际应用与变式-JZTXT

一.二分查找之于STL

lower_bound()可以寻找第一个大于等于的

upper_bound()可以寻找第一个大于的

返回直应用auto承载，或在获取指针时-数组名/-vec.begin()

distance(st.begin(),st.end())也可以获得其中元素个数

和以上两个函数相作用，其用法不言而喻

二.二分法求函数值

使用前提：函数在该区间内有单调性

int bs(int l,int r)
{
    int mid;
    while(l<=r)
    {
        mid=l+(r-l)/2;
        if(check(mid))
        {
            l=mid+1;
            ans=mid;
        }
        else
        {
            r=mid-1;
        }
    }
}//当取值为int类型时的用法

double bs(double l,double r)
{
    double mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if(check(mid))
        {
            l=mid;
        }
        else
        {
            r=mid;
        }
    }
    return mid;
}//当取值为double类型时的用法