三分法

一句话算法

三分法在单峰函数上同时试两个中点，每次丢掉一定不含最优点的一侧。

问题模型

给定一个函数 $f(x)$，它在区间 [l,r] 上满足单峰性：

• 先上升后下降，要求最大值；
• 或先下降后上升，要求最小值。

三分法用于在这个区间内寻找极值点。

核心直觉

二分依赖单调性，三分依赖单峰性。

对求最大值来说，取两个点：

l ---- m1 ---- m2 ---- r

如果 f(m1) < f(m2)，说明从 m1 到 m2 仍然在往更优方向走，最大值不可能在 [l,m1]。

如果 f(m1) > f(m2)，说明过了更优区域后开始变差，最大值不可能在 [m2,r]。

算法步骤

以求最大值为例：

1. 维护候选区间 [l,r]。
2. 取：
   cpp 复制

           
   1
   2
   
           m1 = l + (r - l) / 3
   m2 = r - (r - l) / 3
       

3. 如果 f(m1) < f(m2)，令 l = m1。
4. 否则令 r = m2。
5. 重复足够多轮，或直到区间长度小于精度要求。

求最小值时，把比较方向反过来即可。

算法证明

以单峰最大值为例。

若 f(m1) < f(m2)，最大值不可能在 m1 左侧。因为如果峰顶在 [l,m1]，那么从 m1 到 m2 应该已经处于下降段，应有 f(m1) >= f(m2)，与条件矛盾。

所以可以丢弃 [l,m1]。

同理，若 f(m1) >= f(m2)，最大值不可能在 m2 右侧，可以丢弃 [m2,r]。

每轮都保留包含最优点的区间，因此算法正确。

复杂度分析

浮点三分通常固定迭代次数，例如 100 到 200 次。

• 时间复杂度：$O(T)$，其中 $T$ 是迭代次数。
• 空间复杂度：$O(1)$。

整数三分通常在区间长度较小时停止，再暴力检查剩余整数点。

代码实现

这份模板演示在区间内求函数：

的最大值点。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

double f(double x) {
    return -(x - 3.0) * (x - 3.0) + 10.0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    double left, right;
    cin >> left >> right;

    for (int iter = 0; iter < 200; iter++) {
        double m1 = left + (right - left) / 3.0;
        double m2 = right - (right - left) / 3.0;

        if (f(m1) < f(m2)) {
            left = m1;
        } else {
            right = m2;
        }
    }

    double x = (left + right) / 2.0;
    cout << fixed << setprecision(10) << x << ' ' << f(x) << '\n';
    return 0;
}
    

测试用例

输入：

-10 10

输出近似为：

3.0000000000 10.0000000000

应用分类详解

三分法的本质是在单峰结构中找极值。题目不要求单调，但要求“先变好再变差”时，就要考虑三分。

一、连续函数极值

典型模式： 给出实数函数，要求最大值或最小值。

识别信号： 出现“单峰”“凸函数”“凹函数”“保留若干位小数”。

核心建模： 把答案写成一个关于 x 的函数，在实数区间上三分。

二、整数单峰答案

典型模式： 答案位置是整数，函数值先变好再变差。

识别信号： 出现“选择一个整数位置使代价最小”。

核心建模： 先三分缩小范围，剩余少量整数点暴力检查。

三、参数优化

典型模式： 调整一个参数，使总收益最大或总代价最小。

识别信号： 题面看起来像优化一个连续变量。

核心建模： 证明或观察目标函数具有单峰性，再使用三分。

经典例题

1. luogu-P3382

三分法模板题。适合练习浮点三分和精度控制。

2. 几何最近点问题

当某个点沿线段移动，距离函数可能具有凸性，可以用三分求最小值。

3. 整数参数优化题

若目标函数在整数区间上单峰，可以三分后暴力检查最后几个整数点。