三分

Tanphoon / 2023-08-14 / 原文

给一个先增后减或先减后增数列 \(f[i], i\in[a,b]\) ，可以看作是一个单峰的函数，求最大/小值。

三分法

int l = a - 1, r = b + 1;
while (r - l > 2) {
    int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
    (f[m1] < f[m2]) ? l = m1 : r = m2;
}
int ans = (l + r) / 2;

如果是凹函数，那么 (f[m1] < f[m2]) 改为 (f[m1] > f[m2]) 。

证明 m1 和 m2 能够取到 [a, b] 的所有值

在循环体中始终满足 r - l >= 3

m1 = l + (r - l) / 3 >= l + 1 = a

m2 = r - (r - l) / 3 <= r - 1 = b

m1 >= a, m2 <= b 得证

证明 (l + r) / 2 为峰值

循环结束的前一步 l, m1, m2, r

此时峰值为 max(m1, m2)

如果 f(m1) < f(m2)，l = m1，(m1 + r) / 2 = m2 为较大值

如果 f(m1) > f(m2)，r = m2，(l + m2) / 2 = m1 为较大值

于是循环结束后 (l + r) / 2 为峰值

int extremum(int a, int b, const function<int(int)> f) {
    int l = a - 1, r = b + 1;
    while (r - l > 2) {
        int m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        (f(m1) < f(m2)) ? l = m1 : r = m2; // 凹函数<改>
    }
    return (l + r) / 2;
}

二分法

考虑对数列 \(f\) 求差分数列 \(d\)

则 \(f\) 的峰值一定在 \(d\) 的正负交界处，对 \(d\) 进行二分，查找最后一个正数的位置。

int extremum(int a, int b, const function<int(int)> f) {
    int l = a - 1, r = b + 1;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        f(mid - 1) - f(mid) < 0 ? l = mid : r = mid; // 凹函数<改>
    }
    return l;
}