二分

二分

1.整数二分

用一个性质将区间分为满足性质和不满足性质，答案是二分的边界

情况一

代码分析

int bsearch_1(int l,int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid; //如果mid满足性质缩小区间为[l,mid]
        else l = mid + 1; //如果mid不满足性质缩小区间为[mid+1,r]
    }
}
//最后输出l或r都行，因为二者相等

情况二

代码分析

int bsearch_2(int l,int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid; //如果mid满足性质缩小区间为[mid,r]
        else r = mid - 1; //mid不满足性质缩小区间为[l,mid-1]
    }
}

2.浮点数二分

例：输出x的平方根，x可能为小数

代码分析

#include<iostream>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = 0, r = x; //左右端点
    while (r - l > 1e-8) //l < r只要误差在1e-8即可
    {
        double mid = (l + r) / 2; //注意浮点数没有位运算
        if (mid * mid >= x) r = mid; //mid在答案的左边缩小区间为[l,mid]
        else l = mid; //在答案右边缩小区间为[mid,r]
    }

    cout << l; //输出l或r都行，二者相等
    return 0;
}

知识点

精度：精度eps至少需要比保留位数多2位