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)的最大值。算法的迭代过程如下确定精度设定一个非常小的正数eps例如1e-7或1e-9作为停止迭代的条件。当搜索区间长度(r - l)小于eps时我们认为已经找到了足够精确的极值点位置。计算中间点将当前区间[l, r]三等分。我们需要两个分界点m1 l (r - l) / 3.0m2 r - (r - l) / 3.0注意这里使用浮点数除法以确保点的位置精确。比较函数值计算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。或者简单地归入上述两种情况之一处理对结果影响不大。迭代循环重复步骤2和步骤3直到区间长度(r - l) eps。返回结果迭代结束后区间[l, r]内的任何一点通常取中点(lr)/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 // 示例函数一个开口向下的抛物线最大值在 x2 处值为 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; }关键点解析eps的选择这是精度与效率的权衡。1e-9对于大多数题目足够。如果函数计算非常耗时或者对精度要求不高可以放宽到1e-6或1e-7。在少数极端情况下可能需要1e-12甚至更高。中间点计算务必使用l (r - l) / 3.0而不是l (r - l) / 3。后者是整数除法会导致精度丢失在浮点数三分时是致命错误。m2的计算同理。循环条件while (r - l eps)是标准写法。也有写成for(int i 0; i iterationTimes; i)的固定次数循环见下文。返回值返回(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-9log(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; }注意事项循环条件使用while (r - l 2)。因为当区间长度小于等于3时m1和m2可能相等或导致逻辑混乱不如直接线性扫描更清晰可靠。中间点计算在整数域使用整数除法(r - l) / 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 场景三验证函数单峰性的技巧在比赛中题目通常会明确告诉你函数是单峰的。但在实际应用中如何判断数学分析求二阶导数。对于定义在区间上的连续可导函数如果在区间内二阶导数恒大于0是凸函数有最小值恒小于0是凹函数有最大值。这提供了理论保证。数值试探如果无法求导可以采用采样法。在区间内均匀取若干个点画出函数值的大致趋势观察是否呈现“先增后减”或“先减后增”的形态。虽然不能百分百保证但对于大多数算法题目的数据是有效的。经验判断很多经典模型如距离和时间、成本和产量产生的函数往往是单峰的。实操心得在竞赛中如果题目要求精度很高如1e-12而你的三分法总是WAWrong 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)本身计算非常复杂例如包含复杂的模拟、数据库查询、网络请求那么三分法的效率会很低。优化策略减少迭代次数在满足精度要求的前提下尽量使用较大的eps或较少的固定迭代次数。缓存结果如果f(x)是确定性的纯函数且计算参数是离散的如在整数三分中可以考虑使用记忆化Memoization缓存已计算的结果。但在连续三分中x值几乎不会重复缓存意义不大。并行计算在计算f(m1)和f(m2)时如果它们相互独立且计算资源允许可以尝试并行计算以提升速度。但这通常超出了普通算法题的范畴。5.3 区间初始边界选择不当三分法要求极值点必须在初始区间[l, r]内部。如果极值点在边界上严格的三分法可能无法找到因为每次迭代都舍弃三分之一区间可能把边界点舍掉。诊断与解决如果怀疑极值点在边界可以先将搜索区间向外扩展一些。例如如果理论区间是[0, 100]可以实际在[-10, 110]上搜索。在循环结束后不仅检查区间中点也计算一下f(l)和f(r)与中点结果比较取最优值。对于求最小值问题如果函数单调极值就在边界。此时三分法可能不是最佳选择直接比较端点即可。5.4 问题排查速查表当你提交的三分法代码得到 Wrong Answer 或 Time Limit Exceeded 时可以按此表排查现象可能原因检查点与解决方案WA答案错误1. 函数非单峰。2. 精度eps设置过大。3. 寻找最大值/最小值的逻辑弄反。4. 初始区间[l, r]不包含极值点。1. 绘制函数图像或输出中间值验证单峰性。2. 适当减小eps如从1e-6改为1e-9。3. 仔细检查if (f(m1) f(m2))后的更新逻辑。4. 扩大初始区间范围。TLE超时1. 死循环。2. 函数f(x)计算过于复杂。3.eps设置过小。1. 添加迭代次数计数器并输出或改用固定次数循环。2. 优化f(x)的计算过程。3. 增大eps或改用固定迭代次数。精度不足1.eps设置过大。2. 浮点数累计误差。1. 使用更高的精度要求更小的eps。2. 使用long double类型进行计算。注意long double的精度和范围因编译器和平台而异。整数三分错误1. 循环条件不当导致提前退出或死循环。2. 最终线性查找范围错误。1. 确认使用while (r - l 2)。2. 确认线性查找的循环是for (int i l; i r; i)。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条件或罚函数法。多峰问题对于有多个局部极值的函数三分法会失败。需要模拟退火、遗传算法、粒子群优化等全局优化算法。理解三分法是踏入数值优化世界的一块坚实基石。它清晰的二分或说三分思想、对函数性质的依赖在更高级的算法中都能看到影子。