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

1. 从一道题开始为什么“三分法”是解决单峰函数极值的利器最近在洛谷上刷题又碰到了老朋友P3382。这道题被标记为“【模板】三分法”可以说是算法竞赛入门选手在接触完二分查找后遇到的第一个“看起来像二分但又不是二分”的经典题目。很多朋友第一次做的时候会下意识地想用二分法去逼近极值点结果要么是WA要么是TLE最后看了题解才恍然大悟哦原来函数的形状有讲究方法也得换。这道题的核心是让你在一个单峰函数的给定区间[l, r]上寻找那个唯一的极大值点或极小值点。所谓单峰就像一座山在区间内先严格单调上升到达顶峰后再严格单调下降或者先下降再上升单谷。二分法之所以失效是因为它依赖一个单调的判定条件比如“是否满足某个性质”而单峰函数在极值点两侧的单调性是相反的你无法用一个简单的“是或否”来缩小区间。这时候“三分法”就登场了。它的思想非常直观既然我不知道极值点在哪但我每次可以试探两个点通过比较这两个点的函数值我就能判断极值点更可能在哪一边从而安全地砍掉不可能包含极值点的那部分区间。这个过程像极了我们在黑暗中用手摸索一个凸起物体的最高点左手摸一下右手摸一下哪边感觉更高最高点就更可能在哪边然后我们就朝着感觉更高的方向移动双手重复这个过程。在算法竞赛和许多数值计算场景中三分法是一个基础但极其重要的工具。它解决的是无法求导或求导困难但函数值易于计算且已知函数是单峰的情况下寻找极值点的问题。比起更复杂的梯度下降或牛顿迭代三分法实现简单不易出错在精度和效率上往往有很好的平衡。接下来我们就以洛谷P3382为引子彻底搞懂三分法的原理、实现、细节以及那些容易踩的坑。2. 三分法的核心原理如何像“摸石头过河”一样逼近极值理解三分法关键在于理解它为什么能工作以及它和二分法的本质区别。我们先抛开代码用最直观的几何图像来思考。2.1 单峰函数的几何特征与三分策略假设我们有一个单峰函数f(x)在区间[l, r]上先增后减我们要找极大值点。我们在区间内取两个点m1和m2并且让l m1 m2 r。通常为了对称和简单我们取三等分点m1 l (r - l) / 3,m2 r - (r - l) / 3。计算f(m1)和f(m2)。比较这两个函数值如果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]; // 存储多项式系数题目中n13 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; }几个关键细节精度EPS的设置题目要求输出5位小数这意味着绝对误差至少应小于1e-5。为什么这里设为1e-7这是一个经验值。因为浮点数计算存在累积误差且我们的循环终止条件是r - l EPS。如果我们设EPS1e-5那么最终l和r的差值在1e-5量级取中点后其与真实极值点的误差可能接近5e-6这勉强满足5位小数精度但不够稳健。设为1e-7可以提供更高的保障。通常EPS设为题目要求精度1e-(k2)是安全的。中间点的计算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非常大或非常小前一种写法在数值上稍好一些避免了先乘后除可能带来的溢出或精度问题虽然在此场景下影响微乎其微。更重要的是第一种写法意图更明确。函数f(x)的计算这里使用了霍纳法则秦九韶算法的变种通过一次循环累乘计算多项式值时间复杂度O(n)比直接调用pow函数或逐项计算x^i更高效。返回值的处理循环结束后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^2b*xc)距离平方为(x-xp)^2 (a*x^2b*xc - yp)^2。这是一个关于x的四次函数虽然可能不是全局单峰但在实际问题给定的区间内或者对于开口向上的抛物线距离函数在对称轴附近往往是单谷的。可以在一个合理区间内用三分法尝试。5. 三分法实战中的“坑”与经验之谈理论很美好但一写就WA。下面是我在多年做题和教学中总结的三分法常见陷阱。5.1 最大的坑函数并非严格单峰三分法能正确工作的前提是函数在搜索区间[l, r]内是严格单峰的。如果区间内存在多个极值点多峰那么三分法很可能会收敛到某个局部极值点而非全局极值。洛谷P3382明确给出了多项式函数在[l, r]内是单峰的所以可以直接用。但在实际比赛中题目可能不会明确说明这就需要我们自己判断。如何判断分析函数性质对于多项式高阶多项式很难直接判断。但题目通常会在数据范围或描述上做保证。例如如果题目是求凸多边形的外接圆最小半径关于圆心的某个函数它往往是单峰的。画图或采样在思考时可以尝试代入几个特殊点粗略判断函数的变化趋势。如果条件允许比如打表可以写个程序在区间内均匀采样一些点画出函数值的示意图。警惕“平台”如果函数有一段是平坦的导数恒为零那么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-(k2)或1e-(k3)比较安全。另一种更稳健的终止条件是迭代固定次数例如for(int i0; i100; 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这道题我个人的体会是它不仅仅是一个模板。它强迫你去理解“为什么二分不行而三分可以”去思考函数形态与算法选择之间的关系。在代码实现上固定迭代次数的写法几乎可以成为你的标准板子省心又安全。当你以后遇到一个求极值的问题时第一个要问自己的就是“这个函数在我的搜索区间内是单峰的吗” 如果答案是肯定的那么三分法就是你工具箱里最直接、最可靠的那把扳手。