我使用的二分与三分

前言

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

整数域部分

查询单调递增序列中x或x的后继(最小)

while (l < r) {
    int mid = (l + r) >> 1;
    if(data[mid] >= x) r = mid;
    else l = mid + 1;
}
return data[l];

注意这里要用位移而不是除以二,因为对于负数,除以二是向零取整,而位移是真正的向下取等
查寻单调递增序列中x或x的前驱(最大)

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

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

关于无法取值的情况

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

实数域二分

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

2 thoughts on “我使用的二分与三分

发表评论

电子邮件地址不会被公开。 必填项已用*标注