#AcWing系列课程Level-2笔记——4. 浮点数二分算法

佚名 6年前 (2020-02-12) 算法 848人围观抢沙发百度已收录

浮点数二分算法

编写浮点数二分，记住下面的思路，代码也就游刃有余了！

1.首先找到数组的中间值，mid=(left+right)>>1，区间[left, right]被划分成[left, mid]和[mid , right]。

2.然后通过check(mid)判断中间值是不是满足这个性质，保证落到区间里就对了，check是根据不同的题型编写的。

3.最后就能使用折半，缩小区间了，当认为区间已经很小的时候，比如<=10^-6，其实就找到了答案。

浮点数二分算法的核心

浮点数二分的本质也是边界

浮点数二分因为没有整除，每次都可以严格的缩小一半，所以不需要处理边界，相对简单

浮点数二分算法的代码模板

添加了注释

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;  // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)//如果让你保留四位小数，则eps写成1e-6;如果是保留五位小数，则eps写成1e-7
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;//不需要处理边界了
    }
    return l;
}
作者：yxc
链接：https://www.acwing.com/problem/content/792/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。