三分法：单峰函数极值搜索的核心原理与工程实现

1. 从一道题开始：为什么“三分法”是解决单峰函数极值的利器

最近在洛谷上刷题，又碰到了老朋友P3382。这道题被标记为“【模板】三分法”，可以说是算法竞赛入门选手在接触完二分查找后，遇到的第一个“看起来像二分，但又不是二分”的经典题目。很多朋友第一次做的时候，会下意识地想用二分法去逼近极值点，结果要么是WA，要么是TLE，最后看了题解才恍然大悟：哦，原来函数的形状有讲究，方法也得换。

这道题的核心，是让你在一个单峰函数的给定区间[l, r]上，寻找那个唯一的极大值点（或极小值点）。所谓单峰，就像一座山，在区间内先严格单调上升，到达顶峰后，再严格单调下降；或者先下降再上升（单谷）。二分法之所以失效，是因为它依赖一个单调的判定条件（比如“是否满足某个性质”），而单峰函数在极值点两侧的单调性是相反的，你无法用一个简单的“是或否”来缩小区间。

这时候，“三分法”就登场了。它的思想非常直观：既然我不知道极值点在哪，但我每次可以试探两个点，通过比较这两个点的函数值，我就能判断极值点更可能在哪一边，从而安全地砍掉不可能包含极值点的那部分区间。这个过程，像极了我们在黑暗中用手摸索一个凸起物体的最高点，左手摸一下，右手摸一下，哪边感觉更高，最高点就更可能在哪边，然后我们就朝着感觉更高的方向移动双手，重复这个过程。

在算法竞赛和许多数值计算场景中，三分法是一个基础但极其重要的工具。它解决的是无法求导或求导困难，但函数值易于计算，且已知函数是单峰的情况下，寻找极值点的问题。比起更复杂的梯度下降或牛顿迭代，三分法实现简单，不易出错，在精度和效率上往往有很好的平衡。接下来，我们就以洛谷P3382为引子，彻底搞懂三分法的原理、实现、细节以及那些容易踩的坑。

2. 三分法的核心原理：如何像“摸石头过河”一样逼近极值

理解三分法，关键在于理解它为什么能工作，以及它和二分法的本质区别。我们先抛开代码，用最直观的几何图像来思考。

2.1 单峰函数的几何特征与三分策略

假设我们有一个单峰函数f(x)，在区间[l, r]上先增后减，我们要找极大值点。

1. 我们在区间内取两个点：m1和m2，并且让l < m1 < m2 < r。通常为了对称和简单，我们取三等分点：m1 = l + (r - l) / 3,m2 = r - (r - l) / 3。
2. 计算f(m1)和f(m2)。
3. 比较这两个函数值：
   • 如果f(m1) < f(m2)：这说明什么？想想山的形状。如果m2处的值比m1大，那么极大值点不可能在[l, m1]这个区间里。因为函数在[l, m1]上是递增的（单峰假设），如果极大值点在这里，那么m2在m1右边，函数值应该开始下降，f(m2)应该小于f(m1)。这与我们的结果矛盾。所以，我们可以安全地将左端点l更新为m1。
   • 如果f(m1) > f(m2)：同理，极大值点不可能在[m2, r]这个区间里。因为如果极大值点在右边，那么m1在m2左边，函数值应该还在上升，f(m1)应该小于f(m2)。这与结果矛盾。所以，我们可以将右端点r更新为m2。
   • 如果f(m1) == f(m2)：这种情况在连续函数且m1和m2不重合时，理论上只会在一个非常平坦的平台上发生。对于严格的单峰函数（先严格增后严格减），在极值点两侧不会出现相等的函数值（除非正好在极值点）。但在实际数值计算中，由于浮点数精度，可能会遇到。处理方法是，既然两点值相等，那么极值点一定在它们之间[m1, m2]，我们可以同时收缩两边，令l = m1,r = m2。

这个过程就像我们前面说的“摸石头”：m1和m2就是我们的左右手。右手 (m2) 感觉更高，那最高点肯定在右手方向（或右手位置），我们就可以把左手 (l) 移到原来左手摸的位置 (m1)。反之亦然。

2.2 与二分法的本质区别：判定条件的缺失

为什么二分法不行？二分法通常用于求解方程g(x) = 0的根，或者在有单调性的条件下查找。例如，在一个单调递增序列中找第一个大于等于target的数，我们的判定条件是arr[mid] >= target，这个条件在mid左侧和右侧的布尔值是确定的。但对于求f(x)的极大值，我们没有这样一个可以直接判断“mid是否在极值点右侧”的布尔条件。函数值本身的大小关系，需要两个点才能体现出一侧的趋势，这正是三分法需要两个中间点的根本原因。

2.3 算法复杂度与收敛性

每次迭代，我们将区间长度缩短了大约1/3。假设初始区间长度为L，经过一次迭代，新区间长度至少为(2/3)L（最坏情况，f(m1) == f(m2)，我们缩到[m1, m2]，长度是(1/3)L？这里需要仔细算：m1和m2将区间分成三段，每段长约L/3。如果舍弃左段，新区间为[m1, r]，长度是2L/3；如果舍弃右段，新区间为[l, m2]，长度也是2L/3；如果相等，取[m1, m2]，长度是L/3。所以每次迭代至少缩短到原来的2/3）。因此，算法的迭代次数是O(log_{1.5}(L/eps))，其中eps是我们要求的精度。这和二分法的O(log_{2}(L/eps))是同数量级的，只是底数不同，在实际应用中效率相当。

3. 洛谷P3382：三分法模板题的代码实现与细节剖析

理解了原理，我们来看洛谷P3382的具体实现。题目通常要求保留5位小数，这意味着我们需要一个足够高的精度作为终止条件。

3.1 浮点数三分：标准实现与精度控制

这是最经典的实现方式，适用于函数表达式已知且可计算的情况。

#include <iostream> #include <iomanip> #include <cmath> using namespace std; const double EPS = 1e-7; // 通常比要求精度高两个数量级 double a[15]; // 存储多项式系数，题目中n<=13 int n; double l, r; double f(double x) { double ans = 0; double pow_x = 1; for (int i = 0; i <= n; ++i) { ans += a[i] * pow_x; pow_x *= x; } return ans; } double ternary_search(double l, double r) { while (r - l > EPS) { double m1 = l + (r - l) / 3; double m2 = r - (r - l) / 3; if (f(m1) < f(m2)) { l = m1; // 极值点在[m1, r] } else { r = m2; // 极值点在[l, m2] } } return (l + r) / 2; // 返回区间中点作为近似极值点 } int main() { cin >> n >> l >> r; for (int i = n; i >= 0; --i) { // 注意输入顺序，有时是降幂 cin >> a[i]; } double ans = ternary_search(l, r); cout << fixed << setprecision(5) << ans << endl; return 0; }

几个关键细节：

1. 精度EPS的设置：题目要求输出5位小数，这意味着绝对误差至少应小于1e-5。为什么这里设为1e-7？这是一个经验值。因为浮点数计算存在累积误差，且我们的循环终止条件是r - l > EPS。如果我们设EPS=1e-5，那么最终l和r的差值在1e-5量级，取中点后，其与真实极值点的误差可能接近5e-6，这勉强满足5位小数精度，但不够稳健。设为1e-7可以提供更高的保障。通常，EPS设为题目要求精度1e-(k+2)是安全的。
2. 中间点的计算：m1 = l + (r - l) / 3和m2 = r - (r - l) / 3。绝对不要写成m1 = (2*l + r) / 3和m2 = (l + 2*r) / 3吗？其实在数学上是等价的，但前一种写法(r - l) / 3更清晰地表达了“三等分”的概念，且在某些极端情况下（l和r非常大或非常小），前一种写法在数值上稍好一些（避免了先乘后除可能带来的溢出或精度问题，虽然在此场景下影响微乎其微）。更重要的是，第一种写法意图更明确。
3. 函数f(x)的计算：这里使用了霍纳法则（秦九韶算法）的变种，通过一次循环累乘计算多项式值，时间复杂度O(n)，比直接调用pow函数或逐项计算x^i更高效。
4. 返回值的处理：循环结束后，l和r非常接近。直接返回l或r都可以，但返回(l + r) / 2是更稳妥的做法，因为它位于当前置信区间的中心。

3.2 整数域上的三分：离散情况的处理

有些问题定义在整数域上，例如在一个整数数组（先增后减）中找最大值。此时，区间长度是整数，我们不能简单地取1/3点。

int ternary_search_int(int l, int r) { while (r - l > 2) { // 当区间长度大于2时继续 int m1 = l + (r - l) / 3; int m2 = r - (r - l) / 3; if (f(m1) < f(m2)) { l = m1; } else { r = m2; } } // 此时区间长度 <= 2，暴力检查剩余的点 int ans = l; double max_val = f(l); for (int i = l + 1; i <= r; ++i) { if (f(i) > max_val) { // 找最大值 max_val = f(i); ans = i; } } return ans; }

要点：

• 终止条件不再是r - l > EPS，而是r - l > 2。因为当区间长度小于等于2时，m1和m2可能相等或无法有效区分，继续三分没有意义。
• 最后必须对剩余的几个点（通常不超过3个）进行暴力枚举比较，以确保找到正确的极值点。
• 整数三分的一个常见应用是在凸函数（或凹函数）上寻找最优整数解，例如某些特殊的动态规划优化问题。

3.3 黄金比例三分：一种更优的选点策略

标准三分每次迭代需要计算两次函数值 (f(m1)和f(m2))。有没有办法每次只计算一次函数值？可以，利用黄金比例。

我们不再取三等分点，而是取黄金分割点：设phi = (sqrt(5)-1)/2 ≈ 0.618。我们维护两个点m1和m2，使得m1 = r - phi*(r-l),m2 = l + phi*(r-l)。初始时计算f(m1)和f(m2)。

在迭代中：

• 如果f(m1) < f(m2)，极值点在[m1, r]。我们令新的l = m1，新的m1 = m2，然后只需要计算新的m2对应的函数值即可，因为m2成为了新区间的m1位置，其函数值是已知的。
• 如果f(m1) > f(m2)，极值点在[l, m2]。我们令新的r = m2，新的m2 = m1，然后只需要计算新的m1对应的函数值。

这样，每次迭代只需要计算一次新的函数值，理论上比标准三分节省了约一半的函数计算开销。这在函数f(x)计算非常昂贵时（例如每次f(x)需要运行一个模拟过程）优势明显。

double golden_ternary_search(double l, double r) { const double phi = (sqrt(5) - 1) / 2; // 0.618... double m1 = r - phi * (r - l); double m2 = l + phi * (r - l); double f1 = f(m1), f2 = f(m2); while (r - l > EPS) { if (f1 < f2) { l = m1; m1 = m2; f1 = f2; m2 = l + phi * (r - l); f2 = f(m2); } else { r = m2; m2 = m1; f2 = f1; m1 = r - phi * (r - l); f1 = f(m1); } } return (l + r) / 2; }

注意：黄金比例三分在逻辑上稍复杂，容易在更新点和函数值时出错。在算法竞赛中，除非题目明确卡常数（函数计算极慢），否则标准三分因其实现简单、不易出错而更受欢迎。

4. 三分法的典型应用场景与实战变种

三分法不仅仅用于解多项式极值。任何具有单峰（单谷）性质的函数或序列，都可以尝试用三分法求解极值点。

4.1 距离函数的最小化问题

经典问题：在一条直线上有n个点，其位置为a[i]。求直线上一点x，使得该点到所有点的距离之和f(x) = Σ|a[i] - x|最小。

• 分析：函数f(x)是一个凸函数（先减后增，单谷）。它的最小值点就是这些点的中位数。但如果我们不知道这个结论，或者点不是在一维直线上呢？
• 变种：求一点x，使得到所有点的距离的平方和g(x) = Σ(a[i] - x)^2最小。这个函数是凸的，最小值点在均值处。同样可以用三分法求解。
• 更高维？如果点在一个平面上，求一个点(x, y)使得到所有点的欧氏距离之和最小（斯坦纳点问题近似求解），这是一个更复杂的问题，但有时可以对x和y分别进行三分搜索（即固定x三分y，再固定y三分x，迭代进行），但这需要函数关于每个变量是单峰的，且可能陷入局部最优。

4.2 与单调性结合：解决离散最值问题

有些问题中，我们需要在一个序列里找到一个分界点，使得某个代价函数最小。这个代价函数关于分界点可能是单峰的。

例题想象：你有n个任务，每个任务有一个难度值d[i]。你可以选择一个阈值X，将所有难度< X的任务交给新手做（完成速度慢，单位时间收益低），难度>= X的任务交给专家做（完成速度快，单位时间收益高）。总收益是关于X的函数。随着X增大，交给专家的任务变多，总收益可能先增后减（因为简单的任务给专家做浪费了专家能力，难的任务给新手做又太慢），形成一个单峰函数。这时就可以用三分法求最优的X。

4.3 计算几何中的三分应用

在某些几何问题中，需要求一个点到一条曲线（如抛物线、椭圆弧）的最短距离。距离函数dist(t)（其中t是曲线参数）往往可能是单峰的。这时就可以对参数t进行三分搜索，求距离最小值。

示例：求点(xp, yp)到抛物线y = a*x^2 + b*x + c的最小距离。设抛物线上一点为(x, a*x^2+b*x+c)，距离平方为(x-xp)^2 + (a*x^2+b*x+c - yp)^2。这是一个关于x的四次函数，虽然可能不是全局单峰，但在实际问题给定的区间内，或者对于开口向上的抛物线，距离函数在对称轴附近往往是单谷的。可以在一个合理区间内用三分法尝试。

5. 三分法实战中的“坑”与经验之谈

理论很美好，但一写就WA。下面是我在多年做题和教学中总结的三分法常见陷阱。

5.1 最大的坑：函数并非严格单峰

三分法能正确工作的前提是函数在搜索区间[l, r]内是严格单峰的。如果区间内存在多个极值点（多峰），那么三分法很可能会收敛到某个局部极值点，而非全局极值。洛谷P3382明确给出了多项式函数在[l, r]内是单峰的，所以可以直接用。但在实际比赛中，题目可能不会明确说明，这就需要我们自己判断。

如何判断？

1. 分析函数性质：对于多项式，高阶多项式很难直接判断。但题目通常会在数据范围或描述上做保证。例如，如果题目是求凸多边形的外接圆最小半径（关于圆心的某个函数），它往往是单峰的。
2. 画图或采样：在思考时，可以尝试代入几个特殊点，粗略判断函数的变化趋势。如果条件允许（比如打表），可以写个程序在区间内均匀采样一些点，画出函数值的示意图。
3. 警惕“平台”：如果函数有一段是平坦的（导数恒为零），那么f(m1) == f(m2)可能会频繁发生。我们的代码能处理这种情况（l = m1, r = m2），但收敛速度会变慢，且最终找到的是平台上的任意一点，不一定是题目要求的（比如最左端的点）。

5.2 精度设置的玄学

EPS设多大？这是一个经验问题。

• 设得太小：比如1e-12。由于浮点数的精度限制（double的有效位数约15-16位），当l和r非常大时，(r-l)/3的计算可能已经存在误差，导致循环无法终止（陷入无限循环），或者迭代次数过多导致TLE。
• 设得太大：比如1e-5，可能无法达到题目要求的精度。
• 经验法则：
  • 对于输出k位小数的问题，EPS设为1e-(k+2)或1e-(k+3)比较安全。
  • 另一种更稳健的终止条件是迭代固定次数，例如for(int i=0; i<100; i++)。因为三分法每次缩小区间至原来的~2/3，迭代100次后，区间长度会缩小到原来的(2/3)^100，这是一个极其小的数，对于任何实际精度要求都足够了。这是我最推荐在竞赛中使用的方法，完全避免了精度判断的麻烦和死循环风险。

double ternary_search_fixed_iter(double l, double r) { for (int i = 0; i < 100; ++i) { // 迭代100次 double m1 = l + (r - l) / 3; double m2 = r - (r - l) / 3; if (f(m1) < f(m2)) { l = m1; } else { r = m2; } } return (l + r) / 2; }

5.3 函数值比较与等号处理

在if (f(m1) < f(m2))这个判断中，等号放在哪边？我们的代码是放在else里（即f(m1) >= f(m2)时执行r = m2）。这会导致当f(m1) == f(m2)时，我们收缩右边界。这没问题，因为极值点在[l, m2]内。你也可以选择收缩左边界 (l = m1)，同样正确。两种选择都不会丢掉极值点，只是搜索路径略有不同。保持一种习惯即可。

5.4 针对特定问题的优化：导数与三分法的结合

如果函数f(x)的导数f'(x)比较容易计算，那么问题就转化为了求f'(x)=0的根。而f'(x)在单峰函数的极值点两侧是单调的（极大值点左侧导数为正，右侧为负）。因此，我们可以对f'(x)使用二分法求根！这通常比三分法更快（每次迭代一次函数求值 vs 两次），但前提是你能写出导数表达式并证明其单调性。

对于洛谷P3382的多项式，导数很容易求。如果题目允许，这也不失为一种方法，但它偏离了“三分法模板”的练习初衷。

6. 从三分法到更一般的优化思想

三分法本质上是单峰函数上的搜索算法。它启发我们，对于具有某种凸性（单峰性）的问题，我们可以用比暴力枚举高效得多的方法找到最优解。

• 类比二分答案：二分答案解决的是“判定性问题”的优化（是否存在一个方案满足条件？）。三分法解决的是“单峰函数求极值”的优化。前者需要单调的判定函数，后者需要单峰的目标函数。
• 与梯度下降的对比：梯度下降是寻找函数极小值的通用迭代方法，但它需要计算梯度（导数），且可能陷入局部最优，步长选择也很关键。三分法不需要导数，在单峰区间内能保证找到全局最优，但只适用于一维情况。
• 推广：爬山法与模拟退火：对于多峰函数或者多维情况，我们则需要更复杂的全局优化算法，如爬山法（容易陷入局部最优）、模拟退火（以一定概率跳出局部最优）等。三分法可以看作是这些更高级算法在一维单峰情况下的特例和基石。

最后，关于洛谷P3382这道题，我个人的体会是，它不仅仅是一个模板。它强迫你去理解“为什么二分不行，而三分可以”，去思考函数形态与算法选择之间的关系。在代码实现上，固定迭代次数的写法几乎可以成为你的标准板子，省心又安全。当你以后遇到一个求极值的问题时，第一个要问自己的就是：“这个函数在我的搜索区间内，是单峰的吗？” 如果答案是肯定的，那么三分法就是你工具箱里最直接、最可靠的那把扳手。