1. 项目概述从“三分”到“凸函数”的精确求解在算法竞赛和许多工程优化问题中我们常常会遇到一类特殊的函数它们只有一个“谷底”或“峰顶”。想象一下你在山里找最低点或者在海面上找最高点你不需要走遍每一寸土地只需要用一种高效的策略逐步缩小搜索范围。这就是“三分法”要解决的核心问题。它不是一个简单的数值方法而是一个基于函数凸凹性质的确定性搜索算法专门用于在连续区间上寻找单峰函数的极值点。我最初接触它是在解决一些最优路径、资源分配和参数调优的问题时发现暴力枚举效率低下而导数法又因为函数形式复杂或不可导而无法应用。三分法以其简洁的思想和稳定的性能成为了我工具箱里的常客。所谓“三分”顾名思义就是将当前的搜索区间等分成三份通过比较两个中间分界点的函数值来果断地舍弃掉不可能包含最值的那三分之一区间。这个过程反复迭代区间迅速缩小直到满足我们的精度要求。它解决的是这样一个明确的需求给定一个在区间[l, r]上先严格单调增、后严格单调减或先减后增的函数f(x)找到那个让f(x)取得最大值或最小值的x。这个“单峰”的性质就是“凸函数”在此语境下的实际含义更严格地说用于找最小值的是凸函数找最大值的是凹函数。本文将为你彻底拆解这个算法的原理、实现细节、各种变体以及实战中那些教科书上不会讲的坑。无论你是正在备赛的选手还是遇到类似优化问题的工程师这份“凸函数模板”的深度解析都能让你不仅会套用更能理解其筋骨灵活应用于各种场景。2. 算法核心原理与思路拆解2.1 为什么是“三分”—— 与二分法的本质区别很多人熟悉二分法它用于在单调序列中查找目标值。三分法可以看作是二分法在寻找函数极值问题上的一个类比和扩展。但它们有一个根本性的不同二分法依赖于区间的单调性而三分法依赖于区间的单峰性。二分法每次比较中点值与目标值的关系总能舍弃一半区间因为它明确知道目标在中点的左边还是右边。但对于一个单峰函数你只知道极值点在某处比较一个点的函数值无法告诉你极值点在其左还是右。例如对于一个“先增后减”的函数如果你在上升段取一个点函数值很大但极值点最大值既可能在它右边继续上升也可能在它左边已经过了顶点开始下降。单个点提供的信息不足以做出决策。于是三分法的智慧就体现出来了通过两个点来探测函数的“走势”。将区间[l, r]分为三段取两个中间点m1 l (r - l) / 3和m2 r - (r - l) / 3。比较f(m1)和f(m2)如果f(m1) f(m2)对于找最大值的单峰函数先增后减说明峰值点不可能在m1的左边。因为如果峰值在左边那么从峰值到m1是下降的而m1到m2是上升的这与“先增后减”的定义矛盾。因此我们可以安全地将左端点l更新为m1舍弃[l, m1)这段区间。如果f(m1) f(m2)同理峰值点不可能在m2的右边可以将右端点r更新为m2舍弃(m2, r]。如果f(m1) f(m2)那么峰值点一定在[m1, m2]之间我们可以同时收缩左右端点令l m1,r m2。这样每一次迭代我们都能够确保极值点始终留在新的、更小的区间内并且区间长度以大约2/3的比例缩小。这是一种非常朴素而强大的“夹逼”思想。2.2 “凸函数”在算法中的具体含义在数学优化中凸函数的定义涉及二阶导数非负或Jensen不等式。但在三分法的实用语境下我们所说的“凸函数”通常指的是单峰函数。更准确地当我们寻找最小值时我们要求函数是凸函数形状像碗U型。当我们寻找最大值时我们要求函数是凹函数形状像拱∩型。对于算法本身它只关心函数的单峰性质在定义域内存在唯一极值点且在该点左侧函数单调右侧函数单调方向相反。你的模板必须明确你是在找最大值还是最小值因为这决定了f(m1)和f(m2)比较后该舍弃哪一段区间。一个健壮的模板应该能通过一个参数或简单的逻辑切换来适应这两种情况。注意实际编程中很多“凸函数”并非严格的数学凸函数可能由多个分段函数组成但只要在搜索区间上满足单峰性三分法就适用。这是其应用广泛的重要原因。2.3 算法流程与复杂度分析标准三分法的流程可以清晰地分为以下几步初始化确定搜索区间[l, r]和精度要求eps例如1e-7。迭代收缩当区间长度(r - l)大于eps时循环执行 a. 计算两个三等分点m1 l (r - l) / 3,m2 r - (r - l) / 3。 b. 计算函数值f(m1)和f(m2)。 c.根据寻找最值的类型进行比较 - 找最小值若f(m1) f(m2)则r m2否则l m1。 - 找最大值若f(m1) f(m2)则l m1否则r m2。返回结果迭代结束后区间[l, r]内的任意点通常取(lr)/2都可作为极值点的近似。时间复杂度每次迭代区间长度乘以2/3。假设初始区间长度为L要求最终长度小于eps则迭代次数k满足L * (2/3)^k eps解得k ≈ log_{3/2}(L/eps)。这是一个对数复杂度效率非常高。例如对于L1000,eps1e-7迭代次数大约在 60-70 次左右。空间复杂度为O(1)只需要常数级别的变量存储。3. 核心实现细节与模板解析3.1 浮点数三分模板针对连续函数这是最经典的形式用于自变量为连续实数的函数。模板的核心在于循环条件和比较逻辑。// 寻找凸函数的最小值 double ternary_search_min(double l, double r) { const double eps 1e-10; // 精度根据题目要求调整 while (r - l eps) { double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (f(m1) f(m2)) { r m2; // 最小值在 [l, m2] 区间 } else { l m1; // 最小值在 [m1, r] 区间 } } return (l r) / 2.0; // 返回近似极值点 } // 寻找凹函数的最大值 double ternary_search_max(double l, double r) { const double eps 1e-10; 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; }关键细节与解释精度eps的选择这是浮点数三分的灵魂。eps太小可能因浮点数精度问题陷入无限循环或产生误差eps太大结果不精确。通常如果答案要求输出小数点后k位eps可以设为1e-(k2)。例如要求输出6位小数eps1e-8是个稳妥的选择。有时也采用固定迭代次数如循环100次来替代精度判断这样更稳定。中间点计算务必使用l (r - l) / 3.0而非l (r - l) / 3后者在C/C中会导致整数除法。更安全的写法是m1 l (r - l) / 3和m2 r - (r - l) / 3因为(r-l)是浮点数除以整数3会得到浮点结果。函数f的实现f(x)需要根据具体问题实现。它可能是一个简单的数学表达式也可能是一个需要复杂模拟的过程如计算某种配置下的代价。确保f(x)在[l, r]上是单峰的这是算法正确的前提。3.2 整数三分模板针对离散函数当自变量是整数或者函数定义在整数域上时我们需要整数三分。因为区间长度是整数当区间缩小到很短时m1和m2可能重合需要不同的处理逻辑。// 在整数区间 [l, r] 上寻找凸函数的最小值 int ternary_search_int_min(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)) { r m2; } else { l m1; } } // 区间长度小于等于3暴力枚举剩余点 int min_val f(l); int ans l; for (int i l 1; i r; i) { int val f(i); if (val min_val) { min_val val; ans i; } } return ans; }整数三分的特殊之处循环条件常用while (r - l 2)。因为当区间长度小于等于3时两个三分点m1和m2可能相等或无法有效分割区间此时直接暴力枚举区间内所有整数点更简单可靠。中间点计算使用整数除法。由于是整数(r-l)/3会向下取整。这保证了m1和m2是整数且l m1 m2 r。最终处理循环结束后区间[l, r]通常只剩下2到3个点。对这些点逐一计算函数值并比较得到最终的最优整数解。这是确保结果正确的关键步骤。3.3 通用模板与参数化设计一个更通用的模板可以整合寻找最大值和最小值甚至允许自定义比较函数提高代码复用率。// 通用三分模板 // cmp: 一个函数接受两个double/整数参数a,b当a优于b时返回true。 template typename T, typename Func T ternary_search(T l, T r, Func f, bool (*cmp)(T, T)) { const double eps 1e-10; // 对于浮点数 while (r - l eps) { // 整数版本需改为 while (r - l 2) T m1 l (r - l) / 3; T m2 r - (r - l) / 3; if (cmp(f(m1), f(m2))) { // 如果f(m1)比f(m2)更优根据三分逻辑更新端点 // 对于找最小值更优意味着更小cmp less // 对于找最大值更优意味着更大cmp greater // 更新逻辑需要根据cmp的具体含义来写通常需要特化 // 更实用的写法是下面两个特化版本 } else { // 更新另一个端点 } } return (l r) / 2; } // 实践中更清晰的写法是提供两个特化函数 double ternary_search_min(double l, double r, double (*f)(double)) { while (r - l 1e-10) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (f(m1) f(m2)) r m2; else l m1; } return (l r) / 2; } double ternary_search_max(double l, double r, double (*f)(double)) { while (r - l 1e-10) { 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; }4. 实战应用场景与问题剖析三分法模板之所以重要是因为它能解决一系列看似棘手的问题。下面结合几个典型场景看看如何将问题抽象成单峰函数求极值。4.1 场景一距离最值问题如“灯泡人”问题问题描述在一条数轴上有n个点其位置为a[i]。现在要在这条数轴上找一个点x使得这个点到所有n个点的距离之和f(x) Σ|a[i] - x|最小。这是经典的绝对值和最小问题最优解是中位数。但如果代价不是距离而是距离的平方和f(x) Σ(a[i] - x)^2呢最优解是平均数。如果代价是更复杂的函数比如f(x) Σ sqrt((a[i] - x)^2 C)C为常数这就没有简单的解析解了。抽象与求解函数f(x) Σ sqrt((a[i] - x)^2 C)是一个凸函数可以证明其二阶导非负。因此我们可以直接在数轴的可能范围例如[min(a[i]), max(a[i])]内使用三分法寻找最小值点x。实现时只需编写计算f(x)的函数然后套用浮点数三分求最小值的模板即可。实操心得这类问题的关键在于确定搜索区间[l, r]。通常极值点不会超出数据点的范围所以将l设为min(a[i])r设为max(a[i])是安全的起点。有时根据问题物理意义区间可能需要适当扩大。4.2 场景二最优参数搜索如机器学习中的超参数调优问题描述假设你有一个机器学习模型其性能如准确率是某个连续超参数λ例如正则化系数的函数P(λ)。通过实验你发现P(λ)随着λ从0开始增大先上升后下降形成一个单峰曲线。你需要找到使准确率最高的λ。抽象与求解将P(λ)视为定义在λ的合理范围如[0, 10]上的函数。由于它是单峰的我们可以用三分法来搜索最优的λ。这里的f(λ)就是模型在参数λ下的评估指标计算函数可能涉及训练和验证计算代价较高。注意事项计算成本每次计算f(λ)都可能需要重新训练或验证模型非常耗时。因此在设定三分精度eps时要权衡精度和计算成本。可能只需要中等精度就能找到足够好的超参数。非严格单峰实际中的P(λ)可能不是严格的单峰可能存在多个局部极值。三分法只能找到局部最优且依赖于初始区间。在这种情况下三分法可能不如网格搜索或随机搜索可靠。因此在将三分法应用于此类问题前务必通过初步实验验证函数在选定区间上的单峰性。4.3 场景三几何最值问题如“穿越沙漠”问题描述一个经典问题是从点A到点B中间需要经过一条直线L。在A和B位于直线同侧的情况下求从A到B经过直线L上一点P的最短路径。这是一个光的反射原理问题解是使得入射角等于反射角的点。但如果速度在直线两侧不同呢问题就变成了在直线L上找一点P最小化|AP|/v1 |PB|/v2v1,v2为速度。抽象与求解设P点的坐标由其在直线上的某个参数t表示例如P A0 t * dir其中A0是直线上一点dir是方向向量。那么总时间T(t) |A - P(t)| / v1 |B - P(t)| / v2。可以证明T(t)是关于t的凸函数。因此我们可以对参数t在其有效范围内进行三分搜索寻找使T(t)最小的t。实现技巧计算f(t)时涉及距离计算。确保距离函数正确并且参数t的搜索区间[l, r]涵盖了所有可能的P点通常可以通过几何关系确定。由于是连续函数使用浮点数三分模板。5. 常见陷阱、调试技巧与优化5.1 陷阱一函数非单峰这是三分法失败的最主要原因。如果函数在搜索区间内有多个极值点多峰三分法很可能会收敛到某个局部极值点而非全局最优。排查与验证绘制函数图像如果可能在应用三分法前用程序在搜索区间内以较粗的粒度采样并绘制f(x)的曲线图直观检查单峰性。随机测试在区间内随机选择大量的点对(x1, x2, x3)且x1 x2 x3检查是否满足凸性条件对于最小化问题f(x2) max(f(x1), f(x3))应大致成立。如果大量违反则函数非凸。领域知识从问题本身分析。很多物理、几何问题天然具有凸性。经济学的效用函数、距离的度量等也常常是凸的。5.2 陷阱二浮点数精度与循环终止浮点数运算存在精度损失。如果eps设置得过小如1e-15可能会因为浮点数误差导致r - l始终无法小于eps从而陷入无限循环或提前终止在错误的位置。解决方案设置合理的eps根据问题对答案的精度要求来设定。通常比输出要求高2个数量级足够安全。使用迭代次数限制这是更稳健的做法。根据对数复杂度预先计算一个足够的迭代次数。double ternary_search_min(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)) { r m2; } else { l m1; } } return (l r) / 2; }循环100次区间长度将缩小到原来的(2/3)^100 ≈ 2.5e-18倍对于绝大多数问题都绰绰有余。避免直接比较浮点数相等在比较f(m1)和f(m2)时如果担心精度问题可以使用f(m1) eps f(m2)这样的比较方式但通常直接比较在三分法中问题不大因为决定方向的是大小关系而非精确相等。5.3 陷阱三整数三分的边界处理在整数三分中当区间长度很小时m1和m2可能相等。如果此时仍然按照f(m1)和f(m2)的比较来更新区间会导致区间无法继续收缩。正确做法如前文模板所示当r - l 2时跳出主循环然后暴力枚举区间[l, r]内的所有整数点。这是最安全、最清晰的做法。切勿尝试在m1 m2时进行特殊逻辑处理那样容易出错。5.4 调试技巧打印日志在循环内打印l, r, m1, m2, f(m1), f(m2)的值。观察区间是否在稳步缩小以及函数值的比较是否符合你对函数形状的预期。验证单峰性在最终区间内或随机点上多计算几个f(x)的值检查是否满足“先减后增”或“先增后减”的规律。与暴力枚举对比对于小范围问题可以写一个暴力枚举所有可能解以很小步长采样的程序将三分法的结果与暴力枚举的结果进行对比验证正确性。检查函数实现确保你编写的f(x)函数是正确的。这是三分法的基础往往错误就出在这里。特别是当f(x)涉及复杂计算或模拟时要单独测试这个函数。5.5 性能优化三分法本身已经非常高效。优化点主要在于昂贵的f(x)计算记忆化如果f(x)是纯函数且计算昂贵可以考虑缓存记忆化已经计算过的x对应的f(x)值。但在三分法中x是连续值很难直接命中缓存除非离散化。并行计算在一次迭代中f(m1)和f(m2)的计算是独立的可以并行进行以提升速度。缩小初始区间尽可能利用问题性质缩小[l, r]的初始范围减少迭代次数。例如通过求导、不等式分析或粗略估计确定极值点的大致位置。6. 模板的变体与扩展6.1 黄金分割法三分法将区间分成三等份。一个自然的想法是有没有更优的分割比例黄金分割法0.618法就是一种选择它每次迭代将区间长度缩小到原来的约0.618倍黄金分割比。与三等分相比黄金分割法的优势在于它每次迭代只需要计算一个新的函数值因为其中一个点可以复用上一次迭代的点而三分法需要计算两个新值。当f(x)计算非常昂贵时黄金分割法更有优势。double golden_section_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) { // 找最小值 r m2; m2 m1; f2 f1; m1 r - phi * (r - l); f1 f(m1); } else { l m1; m1 m2; f1 f2; m2 l phi * (r - l); f2 f(m2); } } return (l r) / 2; }6.2 自适应三分与牛顿法对于导数容易求得的凸函数牛顿法或梯度下降法的收敛速度更快二阶收敛。但三分法的优势在于不需要导数信息适用性更广。有一种混合策略先使用几次三分法快速缩小区间然后在足够小的区间内使用牛顿法进行精确求解。这结合了三分法的稳健性和牛顿法的快速收敛性。6.3 高维空间的最优值搜索标准的二分法和三分法只适用于一维搜索。对于多维变量的凸函数优化我们需要其他方法如梯度下降、共轭梯度法或更高级的优化算法。然而有时多维问题可以转化为一系列一维问题例如坐标轮换法每次固定其他变量只优化一个变量这时就可以在该维度上使用一维搜索方法包括三分法。7. 从理解到精通思维训练与题目推荐要真正掌握三分法不能只停留在套模板。我建议通过以下步骤进行思维训练证明单峰性拿到一个问题首先尝试从数学上证明或至少说服自己目标函数在搜索区间上是单峰的。思考它的导数符号变化或者利用几何意义、不等式来论证。手动模拟对于一个小例子用纸笔手动模拟三分法的迭代过程感受区间是如何一步步缩小的。修改模板尝试自己编写支持寻找最大值、最小值的统一模板并增加对整数域和浮点数域的支持。解决变体问题尝试解决一些三分法的变体问题例如寻找一个函数满足f(x) target的x如果函数是单调的用二分如果是凸的可能需要结合三分和函数值比较。经典练习题推荐可在各大在线判题平台搜索基础/模板题直接考察三分法实现通常给出一个明显的凸函数让你求极值点。距离问题变种如前面提到的带权距离和、复杂距离函数如加上平方根的最小化问题。几何问题光线传播、最佳观测点、最短时间路径等问题常能转化为凸函数优化。物理问题涉及能量、时间最优的问题往往具有凸性。经济模型一些简单的成本、收益模型在特定假设下也是凸的。最后记住三分法是一个工具它的威力在于将“寻找最优”这个模糊的目标转化为一个可以通过机械迭代精确逼近的过程。当你遇到一个求最值的问题并且感觉函数值随着参数变化是“先好后坏”或“先坏后好”时不妨想想这会不会是一个单峰函数能不能用三分法来试试这种思维习惯的养成比记住十个模板更有价值。在实际编码中我习惯将三分法函数封装好并附上清晰的注释说明是用于找最大值还是最小值输入区间和精度要求是什么。这样在竞赛或项目遇到相关问题时我可以像调用库函数一样快速、准确地应用它把精力集中在问题建模和函数f(x)的实现上。