kkogoro

我使用的二分与三分
前言二分有很多种写法,而且据说很多人写的二分都不正确或是由瑕疵,(我还没正经写过二分),这里统一我采用的二分是《算...
扫描右侧二维码阅读全文
24
2018/10

我使用的二分与三分

前言

二分有很多种写法,而且据说很多人写的二分都不正确或是由瑕疵,(我还没正经写过二分),这里统一我采用的二分是《算法竞赛进阶指南》中所给出的二分方法

整数域部分

查询递增序列中x或x的后继(大于等于x的最小值)。
查询到的值比最大值大,返回末尾坐标(可以加一个哨兵节点)。(STL的lower_bound返回end())

查询到的值比最小值小,这是合法的,返回头坐标。

inline int search1(int *data, int l, int r, int aim) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if(data[mid] >= aim) r = mid;
        else l = mid + 1;
    }
    return l;
}

注意这里要用位移而不是除以二,因为对于负数,除以二是向零取整,而位移是真正的向下取等

查寻递增序列中x或x的前驱(小于等于x的最大值)。

如果查询的值比最小值小,返回查询最小值的结果

如果查询的值比最大值大,这是合法的,返回最后一个位置

inline int search2(int *data, int l, int r, int aim) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (data[mid] <= aim) l = mid;
        else r = mid - 1;
    }
    return l;
}
代码解析

对于第一种情况, 因为=x也是合法情况,且我们要求最小的等于x的情况,因此要缩小范围 对于第二种情况,因为(l + r) >> 1会出现当r = l + 1时,表达式值为l,因此改为(l + r + 1) >> 1

关于无法取值的情况

第一种$mid$无法取到$r$,第二种$mid$无法取到$l$,因此对于无法查找的情况,我们第一种设范围为$[L,R+1]$,(并加入一个极大值)相应地,第二种为$[L - 1,R]$(并加入一个极小值),如果$l$跃出原区间则表示无法找到。(注意在推导的时候 $l$ 或 $r$ 已经是超出区间的值了)

实数域二分

$eps$一般选取$10^{-(k + 2)}$这个值,$k$是保留位数,


    while (l + eps < r) {
        double mid = (l + r) / 2;
        if (f(mid)) r = mid;
        else l = mid;
    }

当精度不易确定时可以限制二分次数来使精度提高

    for (int i = 0; i < 100; ++i) {
        double mid = (l + r) / 2;
        if (f(mid)) r = mid;
        else l = mid;
    }

三分

模板题

选取区间内的两个点比较它们的函数值并借此确定出极值处于左点的右侧还是右点的左侧,这里如果取三分点是$log\_3 N$的,如果我们选取$mid$两侧就是近似$log\_2 N$的

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    double k[17];
    const double eps = 1e-7;
    double f(double x, int n) {
        double ret = k[0];
        for (int i = 1; i <= n; ++i) {
            double temp = 1;
            for (int  j = 1; j <= i; ++j) {
                temp *= x;
            }
            ret += temp * k[i];
        }
        return ret;
    }
    
    int main() {
        int n;
        double l, r;
        scanf("%d%lf%lf", &n, &l, &r);
        for (int i = n; i >= 0; --i) {
            scanf("%lf", &k[i]);
        }   
        while (l + eps < r) {
            double base = (r - l) / 3;
            double lmid = l + base, rmid = r - base;
            if (f(lmid, n) < f(rmid, n)) l = lmid;
            else r = rmid;
        }
        printf("%.5f", l);
        return 0;
    }
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    double k[17];
    const double eps = 1e-7;
    double f(double x, int n) {
        double ret = 0;
        for (int i = n; i >= 0; --i) {
            ret = ret * x + k[i];
        }
        return ret;
    }
    
    int main() {
        int n;
        double l, r;
        scanf("%d%lf%lf", &n, &l, &r);
        for (int i = n; i >= 0; --i) {
            scanf("%lf", &k[i]);
        }   
        while (l + eps < r) {
            double mid = (l + r) / 2;
            if (f(mid  - eps, n) < f(mid + eps, n)) l = mid;
            else r = mid;
        }
        printf("%.5f", l);
        return 0;
    }
Last modification:November 8th, 2018 at 09:39 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment