二分

二分整型与浮点模板

2021.4.5 更新

重新复习，同样是 yxc 的整数二分模板（同样是二分条件可以将总区间一分为二，题目一般是查询左区间的右端点或者右区间的左端点），但特殊情况下不查询一个端点，查询的是一个区间，查询区间的左端点即查询一般情况下右区间的左端点，查询区间的右端点即查询一般情况下左区间的右端点

//整数二分模板
bool check(int mid)
{

} //性质判断函数

int bsearch1(int l, int r)
{
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid))			//mid 在右区间中
            r = mid;
        else				   //mid 在左区间中
            l = mid + 1;
    }
    return l;
} //[l,r]=>[l,mid],[mid+1,r]

int bsearch2(int l, int r)
{
    while (l < r)
    {
        int mid = (l + r + 1) / 2; //check ture为l = mid时mid = ( l + r + 1) / 2;
        if (check(mid))		//mid 在左区间中
            l = mid;
        else
            r = mid - 1;	//mid 在右区间中
    }
    return l;
} //[l,r]=>[l,mid-1],[mid,r]
//浮点数二分模板
bool check(double mid)
{
}

double bsearch3(double l, double r)
{
    while (r - l > eps)//eps为题目所给精度 （可以往后推几位
    {
        double mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
    return l; //r也可
}