C++三分法详解：从原理到实战，解决单峰函数极值问题

1. 项目概述：从二分到三分，算法思维的进阶

在算法竞赛和日常开发中，我们经常遇到寻找函数极值点的问题。当函数是单调的，经典的二分查找（Binary Search）是我们的不二之选。但现实世界并非总是单调的，很多函数在定义域内先增后减（存在一个峰值）或先减后增（存在一个谷值），比如物理中的抛物线运动、工程中的最优成本控制、甚至是游戏中的伤害计算公式。面对这种单峰函数（Unimodal Function），二分法就束手无策了，因为它依赖于单调性来判断搜索方向的取舍。这时，三分法（Ternary Search）便闪亮登场。

简单来说，三分法是一种用于在单峰函数上寻找极值（最大值或最小值）的算法。它的核心思想与二分法类似，都是通过不断缩小搜索区间来逼近答案。不同之处在于，二分法每次将区间分成两半，而三分法则将区间分成三等分，通过比较两个中间分界点的函数值，来判断极值点位于哪个子区间，从而舍弃掉不可能包含极值点的三分之一区间。这个过程反复迭代，直到区间长度小于我们设定的精度要求。

对于正在学习C++和算法的朋友，尤其是准备信息学竞赛（如NOIP/CSP）的同学，掌握三分法是一个重要的里程碑。它不仅是解决特定问题的利器，更是理解分治思想和数值逼近方法的绝佳范例。接下来，我将结合自己多年的刷题和教学经验，带你彻底吃透C++三分法的原理、实现、细节以及那些容易踩的坑。

2. 三分法的核心原理与数学基础

2.1 什么是单峰函数？

在深入三分法之前，我们必须先明确其适用范围：单峰函数。一个函数f(x)在区间[l, r]上是单峰的，意味着在这个区间内，函数值先严格单调递增（或递减）到达一个极值点（峰值或谷值），然后严格单调递减（或递增）。换句话说，整个区间内有且仅有一个极值点。

• 单峰函数示例：

  • 开口向下的二次函数f(x) = -x^2 + 4x + 1在实数域上是单峰的（有一个最大值）。
  • 开口向上的二次函数f(x) = x^2 - 2x + 3在实数域上是单峰的（有一个最小值）。
  • 正弦函数f(x) = sin(x)在区间[0, π]上是单峰的（有一个最大值），在[π, 2π]上也是单峰的（有一个最小值）。

• 非单峰函数示例：

  • 周期函数如sin(x)在整个实数域上有无数个极值点。
  • 有多个局部极值点的复杂函数。

三分法的有效性完全建立在函数的单峰性假设之上。如果函数不是单峰的，三分法可能收敛到错误的局部极值点，或者根本无法收敛。

2.2 三分法的算法步骤

假设我们在区间[l, r]上寻找单峰函数f(x)的最大值。算法的迭代过程如下：

1. 确定精度：设定一个非常小的正数eps（例如1e-7或1e-9），作为停止迭代的条件。当搜索区间长度(r - l)小于eps时，我们认为已经找到了足够精确的极值点位置。
2. 计算中间点：将当前区间[l, r]三等分。我们需要两个分界点：
   • m1 = l + (r - l) / 3.0
   • m2 = r - (r - l) / 3.0注意，这里使用浮点数除法，以确保点的位置精确。
3. 比较函数值：计算f(m1)和f(m2)。
   • 如果f(m1) < f(m2)： 这意味着最大值点更可能靠近m2。因为函数是单峰的，如果m1处的值比m2小，那么最大值点不可能位于m1的左边区间[l, m1]。我们可以安全地将左边界l更新为m1。
   • 如果f(m1) > f(m2)： 同理，最大值点更可能靠近m1，因此可以将右边界r更新为m2。
   • 如果f(m1) == f(m2)： 在严格的单峰函数中，这种情况只可能发生在极值点恰好位于m1和m2之间。在实际编程中，由于浮点数精度问题，严格相等很少见。一种稳健的处理方式是，此时我们可以同时缩小左右边界，例如令l = m1,r = m2。或者，简单地归入上述两种情况之一处理，对结果影响不大。
4. 迭代循环：重复步骤2和步骤3，直到区间长度(r - l) < eps。
5. 返回结果：迭代结束后，区间[l, r]内的任何一点（通常取中点(l+r)/2或左端点l）都可以作为函数最大值的近似位置。

注意：以上是寻找最大值的流程。如果要寻找最小值，只需在比较时反转逻辑：如果f(m1) > f(m2)，则更新l = m1；如果f(m1) < f(m2)，则更新r = m2。

2.3 与二分法的本质区别

理解三分法和二分法的区别，能帮助你更深刻地理解算法设计。

• 信息利用：二分法每次比较中点与目标值，只利用了一个点的函数值信息（以及单调性）来决定搜索方向。三分法同时利用了两个点(m1, m2)的函数值，通过它们的相对大小来推断极值点的方位。这好比在山上找最高点，二分法只能告诉你“往上走”或“往下走”（如果知道山坡是单调的），而三分法可以告诉你“最高点在东边还是西边”。
• 收敛速度：二分法每次将区间长度减半，收敛速度是O(log2(N))。三分法每次舍弃掉三分之一区间，保留三分之二，收敛速度是O(log3/2(N))，实际上比二分法稍慢一些（因为log3/2(N) = log2(N) / log2(3/2) ≈ 1.71 log2(N)）。但这是为处理非单调问题所必须付出的代价。
• 前提条件：二分法要求单调性，三分法要求单峰性。单峰性是比单调性更宽松的条件，它允许函数有拐点。

3. C++实现三分法的两种姿势

理论讲清楚了，我们来看代码。在C++中实现三分法，主要有两种循环方式：精度控制循环和固定次数循环。我将给出详细的代码和注释。

3.1 基于精度控制的实现（通用推荐）

这是最常用和通用的方法，适用于大多数需要高精度解的场景。

#include <iostream> #include <cmath> #include <iomanip> // 示例函数：一个开口向下的抛物线，最大值在 x=2 处，值为 5。 double func(double x) { return -1.0 * (x - 2.0) * (x - 2.0) + 5.0; } // 三分法寻找函数最大值 double ternary_search_max(double l, double r) { const double eps = 1e-9; // 精度要求，根据题目调整 while (r - l > eps) { double m1 = l + (r - l) / 3.0; double m2 = r - (r - l) / 3.0; if (func(m1) < func(m2)) { l = m1; // 最大值在 [m1, r] 区间 } else { r = m2; // 最大值在 [l, m2] 区间 } } // 循环结束时，l 和 r 非常接近，任取其一即可，通常取中点 return (l + r) / 2.0; } // 三分法寻找函数最小值（修改比较逻辑） double ternary_search_min(double l, double r) { const double eps = 1e-9; while (r - l > eps) { double m1 = l + (r - l) / 3.0; double m2 = r - (r - l) / 3.0; if (func(m1) > func(m2)) { // 注意符号反转 l = m1; // 最小值在 [m1, r] 区间 } else { r = m2; // 最小值在 [l, m2] 区间 } } return (l + r) / 2.0; } int main() { double l = -10.0, r = 10.0; double max_x = ternary_search_max(l, r); double min_x = ternary_search_min(l, r); // 对于这个开口向下的函数，找最小值会收敛到边界 std::cout << std::fixed << std::setprecision(10); std::cout << "在区间 [" << l << ", " << r << "] 上：" << std::endl; std::cout << "函数最大值点 x ≈ " << max_x << std::endl; std::cout << "最大值 f(x) ≈ " << func(max_x) << std::endl; std::cout << "函数最小值点 x ≈ " << min_x << std::endl; // 预期是边界点 -10 或 10 std::cout << "最小值 f(x) ≈ " << func(min_x) << std::endl; return 0; }

关键点解析：

1. eps的选择：这是精度与效率的权衡。1e-9对于大多数题目足够。如果函数计算非常耗时，或者对精度要求不高，可以放宽到1e-6或1e-7。在少数极端情况下，可能需要1e-12甚至更高。
2. 中间点计算：务必使用l + (r - l) / 3.0而不是l + (r - l) / 3。后者是整数除法，会导致精度丢失，在浮点数三分时是致命错误。m2的计算同理。
3. 循环条件：while (r - l > eps)是标准写法。也有写成for(int i = 0; i < iterationTimes; ++i)的固定次数循环，见下文。
4. 返回值：返回(l + r) / 2.0是一个稳健的选择。有时也直接返回l或r。

3.2 基于固定迭代次数的实现

有时，我们可能更关心算法的可预测性，或者函数计算非常复杂，希望严格控制计算次数。这时可以采用固定迭代次数的方法。

double ternary_search_max_fixed(double l, double r) { int iterations = 100; // 固定迭代100次 for (int i = 0; i < iterations; ++i) { double m1 = l + (r - l) / 3.0; double m2 = r - (r - l) / 3.0; if (func(m1) < func(m2)) { l = m1; } else { r = m2; } } return (l + r) / 2.0; }

为什么有效？每次迭代，区间长度大约变为原来的2/3。迭代n次后，区间长度变为初始长度的(2/3)^n。对于iterations = 100，(2/3)^100是一个极其小的数，远超过任何合理的eps要求。这种方法的好处是绝对可控，避免了while循环因精度问题可能产生的无限循环（理论上），并且迭代次数与初始区间长度无关。

如何选择迭代次数？一个经验公式：iterations = log(初始区间长度 / 期望精度) / log(1.5) + 10。其中log以e或10为底均可。+10是为了增加安全余量。例如，初始区间[0, 1000]，要求精度1e-9，log(1e12)/log(1.5) ≈ 80，加上10，约90次迭代足够。直接设为100或200次是竞赛中常见的省心做法。

3.3 整数域上的三分法

三分法不仅可以用于连续函数求浮点数解，还可以用于离散的整数序列，只要该序列是单峰的。例如，在一个先增后减的数组中找到最大值。

// 假设 arr 是一个先严格递增后严格递减的整数数组，找出最大值的下标 int ternary_search_int(int arr[], int n) { int l = 0, r = n - 1; while (r - l > 2) { // 当区间长度大于3时继续 int m1 = l + (r - l) / 3; int m2 = r - (r - l) / 3; if (arr[m1] < arr[m2]) { l = m1; // 峰值在 [m1, r] } else { r = m2; // 峰值在 [l, m2] } } // 区间长度缩小到2或3，直接线性比较 int max_idx = l; for (int i = l + 1; i <= r; ++i) { if (arr[i] > arr[max_idx]) { max_idx = i; } } return max_idx; }

注意事项：

1. 循环条件：使用while (r - l > 2)。因为当区间长度小于等于3时，m1和m2可能相等或导致逻辑混乱，不如直接线性扫描更清晰可靠。
2. 中间点计算：在整数域，使用整数除法(r - l) / 3是正确且高效的。
3. 最终处理：最后在小范围内（通常是2或3个元素）用O(n)的线性查找确定最大值，代码简单不易出错。

4. 三分法的典型应用场景与实战剖析

理解了怎么写，更要明白什么时候用。下面结合几个典型场景，看看三分法如何大显身手。

4.1 场景一：求解凸函数/凹函数的最值问题

这是三分法最直接的应用。许多物理、经济模型可以抽象为凸（Concave）或凹（Convex）函数。

• 例题模型：一个人从A点以速度v1奔跑，到河边某点P，然后以速度v2游泳到B点（B在河对岸）。求从A到B的最短时间。这是一个经典的“将军饮马”问题的变种，时间关于P点位置（一个变量）的函数是单峰的，可以用三分法求解P点坐标。
• 实战代码框架：

  double v1, v2; // 奔跑和游泳速度 double dist_ax, dist_by, river_width; // A到河垂直距离，B到河垂直距离，河宽 double func(double p) { // p是P点离河一侧的距离 double run_dist = sqrt(dist_ax*dist_ax + p*p); double swim_dist = sqrt(dist_by*dist_by + (river_width - p)*(river_width - p)); return run_dist / v1 + swim_dist / v2; } // 然后在区间 [0, river_width] 上对 func(p) 进行三分求最小值。

4.2 场景二：配合其他算法进行优化（三分套三分）

对于有两个独立变量的最优化问题，如果固定一个变量后，关于另一个变量的函数是单峰的，就可以使用“三分套三分”。

• 问题描述：在平面上找一个点，使其到给定的n个点的距离最大值最小（最小覆盖圆问题的一种近似解法）。假设我们猜测一个最大距离R，那么对于每个给定点，可行区域是一个圆。所有圆的交集如果不为空，则R可行。但直接检查交集复杂。一个近似方法是：固定x坐标，求y坐标方向上可行区间的交集。如果对于某个x，存在y使得点(x,y)在所有圆内，则R可行。而“对于某个x，是否存在可行的y”这个判断，可以通过求y方向上可行区间的并集是否为空来实现。但更进一步的，我们可以发现，随着x的变化，可行的y区间长度是一个单峰函数。因此可以用三分法枚举x，对于每个x，再用三分法（或直接计算）求y方向上的最优解。这就构成了两层循环。
• 复杂度警告：三分套三分的复杂度是O(log^2(精度) * 单次计算成本)。如果内层三分每次计算成本是O(n)，那么总成本是O(n log^2(1/eps))，需要谨慎评估数据范围。

4.3 场景三：验证函数单峰性的技巧

在比赛中，题目通常会明确告诉你函数是单峰的。但在实际应用中，如何判断？

1. 数学分析：求二阶导数。对于定义在区间上的连续可导函数，如果在区间内二阶导数恒大于0，是凸函数（有最小值）；恒小于0，是凹函数（有最大值）。这提供了理论保证。
2. 数值试探：如果无法求导，可以采用采样法。在区间内均匀取若干个点，画出函数值的大致趋势，观察是否呈现“先增后减”或“先减后增”的形态。虽然不能百分百保证，但对于大多数算法题目的数据是有效的。
3. 经验判断：很多经典模型（如距离和时间、成本和产量）产生的函数往往是单峰的。

实操心得：在竞赛中，如果题目要求精度很高（如1e-12），而你的三分法总是WA（Wrong Answer），除了检查代码逻辑，一定要怀疑函数是否真的是单峰的。有时题目数据或函数定义会导致区间内存在平台（一段函数值相等的区间），这破坏了严格单峰性，可能导致三分法无法正确收敛。此时可能需要调整策略，比如结合梯度信息或改用其他优化算法。

5. 常见“坑点”与调试技巧实录

即使理解了原理，实现时还是会遇到各种问题。下面是我在多年实践中总结的常见坑点和解决方法。

5.1 浮点数精度陷阱

这是三分法（乃至所有浮点数计算）中最常见的坑。

• 问题1：死循环。循环条件while (r - l > eps)中，如果eps设置得过小（如1e-15），而r和l是double类型，可能会因为浮点数表示精度限制，使得(r - l)的计算值永远无法小于eps，导致无限循环。
  • 解决方案：使用固定迭代次数法，或者为while循环增加一个最大迭代次数限制。

    int max_iter = 100; while (r - l > eps && max_iter--) { // ... 三分逻辑 }

• 问题2：错误比较。在比较f(m1)和f(m2)时，直接使用==判断相等是不可靠的。
  • 解决方案：避免直接判断相等。如果一定要处理相等情况，可以引入一个更小的精度eps2。

    if (fabs(func(m1) - func(m2)) < 1e-12) { // 函数值非常接近，可以任意选择一边，或者同时缩小 l = m1; r = m2; } else if (func(m1) < func(m2)) { l = m1; } else { r = m2; }

    但在绝大多数情况下，不处理相等情况，直接使用<和>比较，算法也能正确工作。
• 问题3：中间点计算不精确。使用m1 = l + (r - l) / 3（整数除法）会导致在整数除法下结果为0，完全错误。
  • 解决方案：牢记浮点数三分时，中间点计算必须用浮点数除法3.0。

5.2 函数计算开销过大

三分法需要多次计算函数值f(x)。如果f(x)本身计算非常复杂（例如包含复杂的模拟、数据库查询、网络请求），那么三分法的效率会很低。

• 优化策略：
  1. 减少迭代次数：在满足精度要求的前提下，尽量使用较大的eps或较少的固定迭代次数。
  2. 缓存结果：如果f(x)是确定性的纯函数，且计算参数是离散的（如在整数三分中），可以考虑使用记忆化（Memoization）缓存已计算的结果。但在连续三分中，x值几乎不会重复，缓存意义不大。
  3. 并行计算：在计算f(m1)和f(m2)时，如果它们相互独立，且计算资源允许，可以尝试并行计算以提升速度。但这通常超出了普通算法题的范畴。

5.3 区间初始边界选择不当

三分法要求极值点必须在初始区间[l, r]内部。如果极值点在边界上，严格的三分法可能无法找到（因为每次迭代都舍弃三分之一区间，可能把边界点舍掉）。

• 诊断与解决：
  1. 如果怀疑极值点在边界，可以先将搜索区间向外扩展一些。例如，如果理论区间是[0, 100]，可以实际在[-10, 110]上搜索。
  2. 在循环结束后，不仅检查区间中点，也计算一下f(l)和f(r)，与中点结果比较，取最优值。
  3. 对于求最小值问题，如果函数单调，极值就在边界。此时三分法可能不是最佳选择，直接比较端点即可。

5.4 问题排查速查表

当你提交的三分法代码得到 Wrong Answer 或 Time Limit Exceeded 时，可以按此表排查：

6. 性能优化与进阶思考

掌握了基础的三分法后，我们可以探讨一些优化和进阶话题。

6.1 黄金分割法：一种更优的区间分割策略

仔细观察标准三分法，每次迭代我们需要计算两个新的函数值f(m1)和f(m2)。有没有可能每次只计算一个函数值，却能达到相似的收敛效率？答案是肯定的，这就是黄金分割法（Golden-section Search）。

黄金分割法的思想是：每次迭代不是三等分，而是按照黄金分割比例φ ≈ 0.618来选取一个中间点。通过巧妙地复用上一个迭代点的函数值，每次只需要计算一个新的函数值。其收敛速度与三分法同阶，但计算量更少。

黄金分割法C++实现框架：

double golden_section_search(double l, double r) { const double phi = (sqrt(5.0) - 1.0) / 2.0; // 黄金比例 ≈ 0.618 const double eps = 1e-9; double m1 = r - phi * (r - l); double m2 = l + phi * (r - l); double f1 = func(m1); double f2 = func(m2); while (r - l > eps) { if (f1 < f2) { // 找最大值，逻辑与三分法类似 l = m1; m1 = m2; f1 = f2; m2 = l + phi * (r - l); f2 = func(m2); } else { r = m2; m2 = m1; f2 = f1; m1 = r - phi * (r - l); f1 = func(m1); } } return (l + r) / 2.0; }

选择建议：在函数f(x)计算非常耗时的场景下，黄金分割法比标准三分法更有优势。在普通算法竞赛中，两者效率差异不大，掌握标准三分法足以应对绝大多数题目。

6.2 三分法与梯度下降的对比

对于连续可导的单峰函数，我们还可以使用梯度下降法（或爬山法）来寻找极值。

• 三分法：不需要导数信息，只依赖函数值。适用于不可导或求导困难的函数。鲁棒性强，但收敛速度相对固定。
• 梯度下降法：利用一阶导数（梯度）信息确定搜索方向。在极值点附近，如果学习率设置得当，收敛速度可能很快（线性收敛或更快）。但需要计算导数，且对学习率敏感，设置不当可能导致震荡或不收敛。

如何选择？

• 如果函数形式简单，能轻松求导，且极值点附近性质良好，梯度下降法可能更快。
• 如果函数是黑盒（只能得到函数值），或者求导复杂，或者需要高可靠性，三分法/黄金分割法是更稳妥的选择。
• 在算法竞赛中，由于题目设计的函数通常形式明确且单峰，三分法因其实现简单、不易出错而成为首选。

6.3 从三分法到更一般的优化算法

三分法解决的是一维、无约束、单峰函数的极值问题。它是更广泛的数值优化领域的一个特例。

• 多维问题：对于多变量函数，有更复杂的算法，如坐标下降法（轮流沿每个坐标轴进行一维搜索）、最速下降法、牛顿法、拟牛顿法等。
• 约束问题：如果变量有约束（如x >= 0），需要用到拉格朗日乘数法、KKT条件或罚函数法。
• 多峰问题：对于有多个局部极值的函数，三分法会失败。需要模拟退火、遗传算法、粒子群优化等全局优化算法。

理解三分法，是踏入数值优化世界的一块坚实基石。它清晰的二分（或说三分）思想、对函数性质的依赖，在更高级的算法中都能看到影子。