浮点数二分算法

一、浮点数二分算法

1.1 编写浮点数二分,记住下面的内容,代码也就游刃有余了!

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

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

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

二、浮点数二分算法的核心

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

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

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

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;
}

查看更多

原文地址:https://www.cnblogs.com/lastk/p/12300866.html