介绍

三分法 (tenary search) 和 二分法(binary search) 类似，只不过三分法可以用于搜索一个 二次函数 的最值。

以搜索二次函数最值为例，假如有一个二次函数存在最大值。

要搜索这个最大值，可以令 $mid = \frac{l+r}{2}$，然后令 $lmid = mid - eps$，$rmid = mid + eps$，然后比较一下 $f(lmid)$ 和 $f(rmid)$ 的大小。

  1. $f(lmid) < f(rmid)$：最大值一定在 $[lmid, r]$ 之间。
  2. $f(lmid) > f(rmid)$：最大值一定在 $[l, rmid]$ 之间。

证明：假如 $f(lmid) < f(rmid)$，那么如果最大值在 $lmid$ 的左边则必然不可能，因为 $rmid$ 离最大值比 $lmid$ 更远。另外一种情况亦然。

例题

例1 洛谷P3382

题意

给定一个 $N$ 次函数，保证 $[l,r]$ 内存在一个点 $x$，使得 $[l,x]$ 单调增，$[x,r]$ 单调减，求 $x$

代码 
#include <bits/stdc++.h>
using namespace std;

const double eps = (double)1e-7;
int n;
double l,r;
double arr[16];

double get(double x) {
    double res = 0;
    double cur = 1.0;
    for (int i = 1; i <= n+1; i++) {
        res += cur * arr[i];
        cur *= x;
    }
    return res;
}

int main() {
    cin >> n;
    cin >> l >> r;
    for (int i = n+1; i >= 1; i--) cin >> arr[i];

    double low = l, high = r;

    while (high - low > 5e-7) {
        double mid = (low + high) * 0.5;
        double lmid = mid - eps, rmid = mid + eps;
        if (get(lmid) < get(rmid)) low = lmid;
        else high = rmid;
    }
    printf("%.7f\n", low);
}

例2 CF1355E

题意

有 $N$ 个柱子，高度分别为 $h_1, h_2, … h_N$。现在有3种操作：

  1. 令一个柱子的高度+1，cost为 $A$
  2. 令一个柱子的高度-1，cost为 $R$
  3. 令一个柱子的高度+1，且令另外一个柱子的高度-1，cost为 $M$

求最小的cost使得所有柱子高度相等？

其中 $1 \leq N \leq 10^5, 0 \leq h_i \leq 10^9$

题解

如果我们枚举最终的高度 $h$，对于每一个 $h$ 都可以在 $\log(N)$ 的时间内计算出来对应的 $cost$。

然后我们会发现，随着 $h$ 的增加，$cost$ 是一个二次函数，具有一个最小值。（证明略）

所以就可以使用三分搜索了！

因为三分搜索的边界不太好处理，所以可以限定一个范围，在范围之内就停止搜索开始暴力枚举。

搜索的部分代码：

ll low = 1, high = 1e9;
while (high - low >= 10) {
    ll mid = (low + high) >> 1;
    ll lmid = mid-1, rmid = mid+1;
    ll lv = solve(lmid), rv = solve(rmid);
    if (lv > rv) low = lmid;
    else high = rmid;
}

for (ll p = low; p <= high; p++) {
    ll r = solve(p);
    ans = min(ans, r);
}