1. 从一道题开始为什么我们需要三分法如果你在洛谷上刷过一些算法题尤其是涉及到函数极值、最优解搜索的题目可能会发现二分法有时会“失灵”。二分法很好它能在有序序列中高效地定位目标但它的前提是“单调性”。当问题变成一个单峰或单谷函数求极值点时二分法就无从下手了因为你无法根据中点与某侧点的比较来决定搜索区间该往哪边收缩。这时一个更强大的工具就该登场了——三分法。我第一次在洛谷上遇到 P3382 这道题时它被标记为“【模板】三分法”。这个标签非常精准因为它几乎涵盖了三分法最经典、最纯粹的应用场景给定一个在定义域[l, r]上单峰的函数f(x)要求你求出其极值点最大值点或最小值点的横坐标x精度通常要求达到1e-5甚至更高。题目不会给你函数的具体解析式而是提供一个黑盒函数你可以传入一个x它会返回对应的f(x)。你的任务就是设计算法用最少的调用次数逼近这个极值点。这不仅仅是理论它在实际问题中无处不在比如调整机器学习模型的超参数学习率大了小了损失都高中间有个最优值、寻找物理实验中的最佳条件、甚至是在游戏AI中为角色寻找一个最佳的射击角度。三分法提供了一种在不知道函数导数或导数难以计算的情况下高效寻找极值点的确定性方法。2. 三分法核心原理如何“掐头去尾”逼近峰值三分法的思想本质上是一种区间缩减策略它比二分法多引入了一个中间点从而能够感知函数的“走势”。2.1 算法流程与形象理解假设我们要求一个单峰函数f(x)在区间[l, r]上的极大值点。单峰意味着函数在区间内先严格单调递增到峰值然后严格单调递减。确定两个中间点我们不像二分法那样只取一个中点mid而是取两个点m1和m2将区间三等分这也是“三分”名字的由来。通常取m1 l (r - l) / 3m2 r - (r - l) / 3这样l m1 m2 r四个点将区间分成了三段。比较函数值舍弃不可能区间计算f(m1)和f(m2)。如果f(m1) f(m2)这说明了什么因为函数是单峰的在达到峰值之前函数值随着x增加而增加。m1 m2且f(m1) f(m2)说明峰值点不可能在m1左边即区间[l, m1]。因为如果峰值在左边那么从m1到m2函数应该下降这与f(m1) f(m2)矛盾。因此我们可以安全地将搜索区间更新为[m1, r]。反之如果f(m1) f(m2)同理峰值点不可能在m2右边即区间[m2, r]因为函数在峰值过后是下降的。我们将搜索区间更新为[l, m2]。如果f(m1) f(m2)在严格单峰函数中这通常只发生在峰值点恰好被m1和m2夹在中间时但为了普适性我们可以将区间更新为[m1, m2]。在实际浮点数计算中直接判断相等很危险通常归入上述两种情况之一处理或者使用一个极小的容差eps。迭代收敛重复步骤1和2每次迭代都将区间长度缩短为原来的约2/3。当区间长度(r - l)小于我们预设的精度要求eps时区间内的任意一点通常取(lr)/2都可以作为极值点的近似解。你可以把它想象成在爬一座形状规则的山单峰你不知道山顶在哪但你可以派两个侦察兵m1和m2去测量他们所在位置的高度。哪个侦察兵的位置更高山顶就更可能在他那边于是你就把大本营挪到他那一边舍弃掉相反方向的那片区域。反复执行你就能快速逼近山顶。2.2 与二分法的本质区别这是理解三分法的关键。二分法依赖于“有序性”和“判定条件”。在有序数组中找值或者解方程f(x)0f(x)单调我们通过比较mid处的值与目标值能明确知道解在左半区间还是右半区间。三分法处理的是“凸性”单峰/单谷是凸函数的一种特例。它不比较函数值与某个目标值而是比较区间内两个不同点的函数值通过函数值的相对大小来判断极值点所在的“方向”。它削减区间依赖的是函数的形状信息而非单调性。注意三分法要求函数在搜索区间内是严格单峰或单谷的。如果函数有多个极值点多峰标准三分法很可能会收敛到某个局部极值点而非全局最优。这是其应用的前提也常常是题目设计的隐含条件。3. 洛谷P3382模板题实战从理解到AC我们以洛谷 P3382 为例将上述原理转化为具体的代码。题目通常要求保留5位小数这意味着我们的精度eps需要设置得比1e-5更小例如1e-7或1e-8为四舍五入留出余地。3.1 代码实现与逐行解析这里给出一个清晰、标准的C实现并附上详细注释。#include iostream #include iomanip #include cmath using namespace std; const double eps 1e-7; // 设置精度要求通常比输出精度高1-2个数量级 int n; double l, r, coe[15]; // 系数数组假设多项式最高次数为14 // 计算多项式函数值 f(x) double f(double x) { double ans 0; double pow_x 1; // x^0 for (int i 0; i n; i) { ans coe[i] * pow_x; pow_x * x; // 依次计算 x^1, x^2, ... } return ans; } // 三分法求单峰函数最大值点 double ternary_search(double l, double r) { while (r - l eps) { // 当区间长度大于精度要求时继续迭代 double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (f(m1) f(m2)) { l m1; // 峰值在 [m1, r] 区间 } else { r m2; // 峰值在 [l, m2] 区间 } } return (l r) / 2.0; // 返回区间中点作为近似极值点 } int main() { cin n l r; for (int i n; i 0; --i) { // 注意题目输入系数顺序通常从高次到低次 cin coe[i]; } double ans ternary_search(l, r); cout fixed setprecision(5) ans endl; return 0; }关键点解析精度eps的设置这是三分法的“停止条件”。eps不能设得太大否则精度不达标也不能设得太小否则可能因浮点数精度问题陷入死循环或者迭代次数过多。一般规则是eps设为输出精度要求的1/100到1/10。例如要求输出5位小数 (1e-5)eps设为1e-7是安全且高效的选择。中间点的计算m1 l (r - l) / 3.0和m2 r - (r - l) / 3.0。一定要用(r - l) / 3.0而不是(r - l) / 3后者在C中是整数除法如果l, r是整数会导致错误。更安全的写法是m1 l (r - l) / 3和m2 l (r - l) / 3 * 2但前者对称性更好理解。区间更新逻辑if (f(m1) f(m2)) l m1;这是求最大值的逻辑。如果求最小值单谷函数条件应反过来if (f(m1) f(m2)) l m1;或者保持判断不变但更新区间时取另一侧。务必根据题目要求明确是求极大值还是极小值。返回值循环结束后l和r非常接近取它们的平均值(lr)/2作为最终结果比单独取l或r更稳定。3.2 一个极易出错的核心细节整数域上的三分P3382 是浮点数三分。但有时我们会遇到定义域为整数的三分问题例如某些离散优化问题。这时循环条件while (r - l eps)不再适用因为r-l是整数差。整数三分的写法// 在整数区间 [l, r] 上三分求极大值点 (l, r 为整数) 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 2因为当区间长度缩小到3或更小时m1和m2可能会重合例如l1, r3m12, m22导致无法通过比较来缩减区间。此时最稳妥的做法是退出循环对区间内剩下的少数几个点最多3个进行暴力计算比较找出最优解。这是整数三分与浮点数三分在实现上的一个重要区别也是新手常踩的坑。4. 三分法的典型应用场景与变形掌握了模板我们来看看三分法能解决哪些实际问题以及它的一些常见变体。4.1 经典应用场景枚举凸函数/凹函数的最值问题这是三分法的“主战场”。例如距离最小化在一条直线上有若干个点求直线上一点使该点到所有给定点的距离之和最小。这个距离和函数是一个凸函数V形可以用三分法求其最小值点。费用最优化某些生产成本或时间成本函数是凸的比如随着产量增加边际成本先降后升。物理中的极值问题如寻找光在两种介质中传播时间最短的路径斯涅尔定律对应的角度时间函数可能是凸的。结合其他算法的搜索三分法可以作为外层搜索框架内层嵌套其他算法。三分答案这是竞赛中非常常见的技巧。当一个问题具有单调性时我们用二分答案当判定函数check(mid)的值关于mid是单峰函数时我们就可以用“三分答案”。例如寻找一个最优的参数使得系统的某个性能指标如公平性、效率最高而这个指标关于参数的变化可能先增后减。多元函数降维对于某些多元函数如果可以固定其他变量证明其关于某一个变量是单峰的那么可以在该维度上使用三分法结合循环或递归处理其他维度。这类似于坐标下降法的思想。4.2 黄金分割三分一种更高效的变体标准三分法每次迭代需要计算两个新点的函数值 (f(m1),f(m2))并将区间缩短为原来的2/3。有没有可能用更少的函数求值次数达到同样的收敛效果黄金分割法Golden-section search就是答案。它的思想是每次迭代只计算一个新点的函数值并利用黄金分割比例φ ≈ 0.618来保持区间的对称缩减。算法简述初始化区间[a, b]计算两个初始点x1 b - φ*(b-a)x2 a φ*(b-a)计算f(x1)和f(x2)。比较f(x1)和f(x2)类似三分法更新区间。关键来了更新区间后有一个点函数值已知会落在新区间内成为新的分割点。我们只需要再计算一个新区间端点的函数值即可进行下一次比较。这样除了第一次迭代需要计算2次函数值后续每次迭代只需要计算1次。对比与选择效率黄金分割法函数求值次数更少对于计算f(x)非常耗时的场景如每次求值都需要运行一个复杂模拟优势明显。收敛速度两者的收敛阶都是线性的但常数因子不同。黄金分割法理论上略优。实现复杂度标准三分法逻辑更直观更容易写对。黄金分割法需要注意维护哪个点的函数值是已知的代码稍复杂。建议在算法竞赛中标准三分法因其简单可靠足以应对绝大多数题目。只有在明确知道函数求值是性能瓶颈且精度要求极高的数值计算课题中才需要考虑实现黄金分割法。5. 避坑指南与实战经验总结在实际使用三分法解决问题时有几个陷阱需要特别注意。5.1 常见错误与调试方法前提条件不满足非单峰这是最致命的错误。如果函数在[l, r]区间内不是严格单峰三分法可能收敛到错误的点或者行为不可预测。如何验证在编写代码前如果可能尽量画出函数在区间内的大致图像可以采样一些点。在竞赛中这通常依赖于对问题性质的数学分析。如果题目明确说是“单峰”那就可以直接用。精度问题导致的死循环或精度不足死循环浮点数三分中如果eps设置得过小如1e-12而l和r的差值由于浮点数精度限制无法再减小可能会满足r - l eps恒成立导致while循环无法退出。安全的做法是同时设置最大迭代次数作为双重保险。int iteration 0; while (r - l eps iteration 100) { // 例如最多迭代100次 // ... 三分逻辑 iteration; }精度不足eps设置过大循环提前结束导致结果有效位数不够。牢记eps与输出精度的关系。更新区间时等号处理在f(m1) f(m2)时理论上峰值在[m1, m2]之间。一种稳健的写法是if (f(m1) f(m2)) { l m1; } else if (f(m1) f(m2)) { r m2; } else { // 相等或非常接近 l m1; r m2; }对于浮点数更常用的是直接使用和因为严格相等的概率极低。但在整数三分或某些特殊函数中等号情况需要仔细考虑。5.2 三分法与其他搜索算法的对比选型知道何时不用三分法和知道何时用一样重要。vs 二分法如果问题具有单调性永远优先选择二分法。二分法每次将区间减半收敛速度是O(log n)比三分法的O(log_{1.5} n)更快且逻辑更简单。只有在确认函数具备凸性但不具备单调性时才选用三分法。vs 梯度下降/牛顿法对于可导且导数易求的函数使用基于梯度的方法如梯度下降、牛顿法通常收敛更快达到二次收敛。三分法的优势在于它是一种直接搜索法不需要导数信息对函数光滑性要求低鲁棒性更强。vs 暴力搜索当定义域是连续的、范围很大时暴力枚举网格点计算量巨大且精度控制麻烦。三分法能以对数级的速度将区间缩小到所需精度效率极高。5.3 个人心得把三分法作为一种思维工具经过多年的刷题和项目实践我发现三分法最重要的价值不仅仅是那个模板代码更是一种优化思维。当你面对一个求最优解的问题时可以按以下步骤思考定性分析我要求解的目标函数或评价指标关于决策变量其变化趋势是什么是单调的还是先升后降或先降后升能不能通过数学推导或直观感受证明其单峰性定量验证如果难以严格证明能否通过小范围采样画图来观察趋势在算法竞赛中题目描述常常会给出“单峰函数”的提示。工具选择确认单峰性后三分法就是一个强有力的候选工具。接着考虑定义域连续实数还是离散整数、精度要求、函数求值成本来选择标准三分、整数三分还是黄金分割。编码与测试实现模板并设计一些边界用例测试比如极值点就在区间端点l或r处的情况。最后再分享一个调试小技巧在实现三分法时可以增加一些调试输出打印出每一轮迭代的l, m1, m2, r, f(m1), f(m2)。这能帮你直观地观察区间是如何缩小的以及函数值的比较是否符合预期对于快速定位逻辑错误非常有帮助。尤其是在处理整数三分或者边界条件复杂的题目时这个习惯能节省大量时间。