1. 从“二分”到“三分”当函数不再单调在算法竞赛和编程面试中二分查找Binary Search几乎是每个程序员都耳熟能详的利器。它之所以强大是因为它完美地利用了单调性——无论是数组的单调递增还是函数值的单调变化只要我们能确定目标值在某个区间内并且这个区间内的函数是单调的我们就能以 O(log n) 的效率逼近答案。二分查找的核心思想是“每次排除一半的搜索空间”这听起来既高效又优雅。但现实世界中的问题往往比单调性更复杂。想象一下你是一个无人机飞手正在规划一条从A点到B点的飞行路径目标是让总能耗最低。能耗可能和飞行速度、飞行高度有关。速度太慢飞行时间太长基础能耗高速度太快空气阻力呈平方甚至立方增长能耗也会剧增。这中间必然存在一个“甜蜜点”——一个让总能耗最低的最佳速度。这个“总能耗-速度”函数很可能就是一个单峰函数函数值先下降到达一个最低点谷底后再开始上升。这个最低点我们称之为极小值点。反过来如果函数先上升后下降那个最高点就是极大值点。单峰函数是凸函数或凹函数在特定区间上的表现。面对一个单峰函数传统的二分查找就失灵了。因为你无法仅仅通过比较中点的函数值就确定目标极值点是在左半边还是右半边。例如你比较了区间中点mid和其右侧一点mid1的函数值发现f(mid) f(mid1)。在单调递增函数中这意味目标在右侧。但在单峰函数中这有两种可能要么mid和mid1都位于极值点左侧函数正在上升要么mid位于极值点右侧而mid1更靠右函数正在下降。仅凭两个点的比较信息不足以做出决策。这就是“三分搜索”Ternary Search登场的时刻。它的核心思想可以概括为既然两个点不够那我就用三个点来“感知”函数的走势。通过选取区间内的两个内分点比较它们的函数值我们就能可靠地判断极值点位于哪三分之一区间内从而每次缩小三分之一的搜索空间。虽然每次迭代的收缩比例2/3略低于二分查找的1/2导致理论常数稍大但它成功地将二分查找“每次排除一半”的思想推广到了“每次排除三分之一”来解决单峰函数极值问题。对于无法求导或导数计算复杂的离散函数、模拟函数三分法提供了一种稳定、通用的数值求解方案。2. 三分法的核心原理如何用三个点确定走势理解三分法关键在于弄清楚它如何通过两个内分点来确定极值点的位置。我们以在区间[l, r]上寻找极小值点为例寻找极大值点的逻辑完全对称。首先我们在区间内选择两个点m1和m2通常将它们选在区间的三等分点附近这也是“三分”名称的由来。更常见的、精度更高的做法是选取两个黄金分割点但三等分点更直观。设m1 l (r - l) / 3m2 r - (r - l) / 3显然l m1 m2 r。现在我们计算f(m1)和f(m2)。对于寻找极小值的情况逻辑如下如果f(m1) f(m2)这告诉我们在m1和m2这两个点中m1处的函数值更小。考虑极小值点的位置。由于函数是单峰的先降后升极小值点左侧函数下降右侧函数上升。如果极小值点在m2的右侧那么从m1到m2再到极小值点函数应该先上升过m2后不对如果极小值点在m2右边那么m1和m2都位于极小值点左侧函数在[m1, m2]区间应该是单调递增的因为还没到谷底。但这与f(m1) f(m2)矛盾吗不矛盾f(m1) f(m2)正说明在[m1, m2]区间函数是递增的所以m1和m2都在极小值点左侧是可能的。然而还有另一种可能极小值点在m1和m2之间。此时m1在极小值点左侧下降段m2在极小值点右侧上升段同样满足f(m1) f(m2)因为m1比m2更靠近谷底不一定如果m1离谷底很近而m2刚过谷底f(m1)可能小于f(m2)。关键推理来了无论哪种情况极小值点都不可能位于m2的右侧。为什么假设极小值点在m2右侧。那么m1和m2都位于极小值点左侧的“下降-上升”曲线的上升段之前即它们都在谷底左侧的下降段。在下降段函数值随着x增加而减小。由于m1 m2我们应该有f(m1) f(m2)。但这与我们已知的f(m1) f(m2)相矛盾。因此当f(m1) f(m2)时我们可以安全地排除掉(m2, r]这个区间将搜索范围缩小到[l, m2]。因为极小值点一定不在m2的右边。如果f(m1) f(m2)同理分析此时m2处的函数值更小。运用对称的逻辑我们可以得出结论极小值点不可能位于m1的左侧。因为如果那样m1和m2将都位于极小值点右侧的上升段应有f(m1) f(m2)矛盾。因此我们可以排除掉[l, m1)这个区间将搜索范围更新为[m1, r]。如果f(m1) f(m2)在连续函数中这种情况通常意味着m1和m2位于极小值点的两侧且距离谷底“距离”相等函数值相同。此时极小值点一定在[m1, m2]之间。我们可以安全地缩小区间为[m1, m2]。在离散或存在平台区的函数中我们可以将其归入上述任意一种情况处理通常不会影响最终收敛到极值点所在的区间。通过这样一轮比较我们确保了极值点一定留在新的、更小的搜索区间内。不断重复这个过程直到区间长度小于我们预设的精度eps此时区间内的任意一点通常取中点都可以作为极值点的近似解。注意上述推导基于函数是严格单峰的假设。如果函数存在平台一段相等的值或者多个极值点三分法可能会失效或收敛到错误的极值点。因此应用三分法的前提是确认或强烈怀疑目标函数在搜索区间内是单峰的。2.1 整数三分离散世界中的极值搜索当定义域是整数时我们进行的是整数三分。此时区间[l, 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; // 排除(m2, r] } else { l m1; // 排除[l, m1) } } // 此时区间[l, r]长度3暴力枚举剩下的点找最小值 int ans f(l); for (int i l 1; i r; i) { ans min(ans, f(i)); }循环条件r - l 2确保了在循环体内m1和m2是两个不同的整数。退出循环后区间内最多剩下3个整数点直接比较即可避免了因精度问题导致的死循环。3. 三分搜索的通用模板与实现细节下面提供一个用于求解连续函数极小值的、基于精度控制的浮点数三分模板C实现。这个模板清晰地区分了l,r,m1,m2并包含了防止无限循环的迭代次数限制。// 三分搜索模板 (求凸函数极小值) double ternary_search(double l, double r) { const double eps 1e-8; // 精度根据题目要求调整 const int iter_limit 100; // 迭代次数限制防止死循环 int iter 0; while (r - l eps iter iter_limit) { iter; 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; // 返回近似极值点 }关键参数解析精度eps这是循环终止的条件。当搜索区间长度r - l小于eps时我们认为已经找到了足够精确的极值点位置。eps的设置需要权衡精度和效率。对于大多数题目1e-8或1e-7是一个安全的选择。如果函数值变化非常平缓可能需要更小的eps如果对精度要求不高可以适当调大以加快速度。迭代次数限制iter_limit这是一个重要的安全措施。理论上三分法总会收敛。但在实际编程中由于浮点数的精度限制可能会出现r - l始终无法小于eps的情况例如在极值点附近函数非常平坦。设置一个迭代上限如100或200次可以强制循环退出避免超时。100次迭代足以将初始区间长度缩小到原来的(2/3)^100 ≈ 3e-18倍对于绝大多数问题足够了。返回值通常返回当前区间[l, r]的中点。因为当循环结束时极值点必然落在这个很小的区间内中点是一个合理的近似。模板的使用与变体求极大值只需将比较条件反转即可。即如果f(m1) f(m2)则r m2否则l m1。或者更简单的方法定义一个g(x) -f(x)然后对g(x)求极小值结果是一样的。整数三分如前所述循环条件改为while (r - l 2)并在循环后暴力枚举剩余点。黄金分割比例更优的选择点比例是黄金分割比φ ≈ 0.618。即取m1 l (r - l) * (1 - φ),m2 l (r - l) * φ。这样每次迭代的区间收缩比例是固定的φ理论上比三等分法效率稍高一点但代码复杂度略有增加三等分法在竞赛中已完全够用。4. 实战应用识别问题与构建目标函数三分法本身是一个框架其威力完全体现在你如何将它应用于具体问题。这分为两步1) 识别出问题可以转化为单峰函数求极值2) 正确构造出这个目标函数f(x)。4.1 经典例题解析士兵找宿舍问题问题描述一条笔直的大路上有N个士兵他们的位置已知坐标p[i]。现在要建立一个宿舍使得所有士兵从宿舍出发再回到宿舍比如早上从宿舍去站岗晚上回宿舍所走的总距离最小。士兵可以同时移动求这个最小总距离。分析与建模决策变量宿舍的位置记作坐标x。目标函数总距离f(x)。对于位置在p[i]的士兵他需要走|p[i] - x|的距离到达宿舍再走同样的距离回来所以贡献是2 * |p[i] - x|。因此f(x) 2 * Σ|p[i] - x|。函数性质绝对值函数|p[i] - x|是一个 V 型函数先减后增多个 V 型函数的和f(x)是一个分段线性凸函数形状像一个碗。它在整个实数域上是凸的并且最小值点就在所有士兵位置的中位数处。但即使你不知道中位数这个结论你也可以观察到f(x)是一个明显的单峰函数凸函数因此可以直接在[min(p), max(p)]区间上使用三分法求其最小值。代码框架double p[N]; // 士兵位置 int n; double f(double x) { double sum 0; for (int i 0; i n; i) { sum fabs(p[i] - x) * 2; // 往返距离 } return sum; } double solve() { double l *min_element(p, p n); double r *max_element(p, p n); return ternary_search(l, r); // 使用前面的三分模板 }4.2 进阶例题光照强度问题Lighting问题描述你有一条长度为 L 的线段。上面有 N 盏灯第 i 盏灯在位置a[i]照明强度为I[i]。在位置 x 处接收到的光照强度定义为S(x) Σ( I[i] / ( (x - a[i])^2 d^2 ) )其中 d 是一个给定的常数防止分母为零。现在要在该线段上找一个点使得该点的光照强度最小。求这个最小强度值。分析与建模决策变量点的位置x。目标函数f(x) S(x)即该点的总光照强度。函数性质每一项I[i] / ((x - a[i])^2 d^2)都是一个关于x的“钟形”函数类似正态分布曲线在x a[i]处取得最大值I[i]/d^2向两边对称衰减。多个这样的“钟形”函数相加得到的f(x)是一个连续、平滑、可导的函数。它的图像是多个波峰叠加。我们需要找的是最小值。关键洞察虽然整个函数可能有多个局部极小值因为波峰叠加会产生波谷但题目通常保证或通过数据范围暗示在给定的线段[0, L]上f(x)是一个单谷函数凸函数。这是因为当灯的位置分布相对均匀时叠加效应会使函数两端较高中间较低。因此我们可以假设在[0, L]区间上f(x)是单峰的有一个极小值从而应用三分法。三分搜索在[0, L]区间上对f(x)进行三分求极小值。这个例子比上一个复杂因为它涉及更复杂的函数形式。它考验的是你将实际问题抽象成数学函数并判断其是否具有单峰性质的能力。在实际比赛中有时需要通过观察函数形式、求导分析或者基于题目背景的合理猜测来做出判断。4.3 避坑指南什么情况下不能用三分三分法不是万能的错误应用会导致错误答案甚至死循环。以下情况需要警惕非单峰函数这是最根本的禁忌。如果函数在搜索区间内有多个极值点多峰函数三分法可能会收敛到某个局部极值点而非全局最优。例如函数sin(x)在[0, 10π]上有多个波峰波谷。平台区如果函数有一段是常数平台三分法在比较f(m1)和f(m2)时如果相等按照我们的模板会执行l m1。这可能导致算法在平台区来回震荡收敛变慢。不过只要最终极值点在区间内算法仍会收敛到平台上的某个点。离散函数与边界对于整数三分要特别注意边界条件。如果极值点恰好就在边界l或r上我们的模板循环条件r-l2在暴力枚举阶段能正确处理。但要确保初始区间[l, r]包含了可能的极值点。精度与迭代浮点数三分中eps设置过小配合没有迭代限制在函数非常平坦的区域可能导致无限循环。务必设置迭代次数上限。函数计算成本三分法每次迭代需要计算两次函数值f(m1)和f(m2)。如果f(x)的计算非常昂贵例如需要运行一次复杂的模拟那么三分法的开销可能变得不可接受。此时需要考虑是否能用求导等解析方法或者使用更高效的优化算法如梯度下降。个人经验在竞赛中如果题目要求输出一个实数答案并且描述中出现了“最小化/最大化某个量”、“找到最优的位置/参数”这类词语同时你能够将这个“量”写成一个关于决策变量的数学表达式就应该立刻考虑三分法。先在心里或纸上简单画一下这个函数可能的形状想想端点值、中间值如果感觉它像是一个“碗”或者“拱形”那么三分法就值得一试。5. 调试技巧与效率优化即使理解了原理和模板在实际编码中也可能遇到各种问题。这里分享一些调试和优化三分法的经验。5.1 如何验证三分法的正确性打印搜索过程在三分循环内打印出每一轮的l, r, m1, m2, f(m1), f(m2)。观察区间是否在稳步缩小以及缩小的方向是否符合逻辑f(m1)f(m2)时r向左缩。与暴力枚举对比对于小范围数据例如整数定义域且范围很小或者可以离散化采样的情况写一个暴力程序枚举所有可能点或密集采样计算f(x)找出最小值点及其函数值。将三分法的结果与暴力结果对比验证是否一致。绘制函数图像如果可能用 Python 的 Matplotlib 等工具在搜索区间内采样几百个点画出y f(x)的图像。直观地检查它是否确实是单峰的以及三分法找到的点是否在谷底/峰顶附近。检查边界条件单峰函数的极值点有可能就在边界上。确保你的三分法初始区间[l, r]包含了边界并且算法在边界处也能正确工作例如对于整数三分最后的暴力枚举包含了l和r。5.2 三分法的效率与常数优化减少函数计算次数这是最大的优化点。在f(m1) f(m2)的情况下我们更新r m2。注意下一轮迭代的m2很可能等于这一轮的m1。因此我们可以复用函数值避免重复计算。double ternary_search_optimized(double l, double r) { const double eps 1e-8; while (r - l eps) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; double f1 f(m1); double f2 f(m2); if (f1 f2) { r m2; // 下一轮的 m2_new 可能等于当前的 m1但 f(m1) 已经计算过了。 // 为了简化代码通常不刻意保存除非f(x)计算极其昂贵。 } else { l m1; } } return (l r) / 2; }对于计算极其昂贵的f(x)可以增加逻辑来缓存f(m1)和f(m2)用于下一轮迭代。整数三分的循环条件while (r - l 2)是安全且高效的标准写法。有些写法用while (l r)并在内部处理m1和m2相等的情况但更容易出错。坚持使用2的条件和事后枚举代码更清晰健壮。精度与迭代次数的权衡如果题目对精度要求不高例如只要求输出整数或保留少量小数可以适当增大eps如1e-5以减少迭代次数。同时迭代上限iter_limit可以设为log(初始区间长度/eps) / log(1.5)的近似值再加一些余量。5.3 三分法与其他优化算法的对比vs. 二分查找二分用于单调函数找特定值或边界三分用于单峰函数找极值。二者思想同源分治但应用场景不同。vs. 求导法如果函数f(x)容易求导那么令f(x)0解方程往往是更直接、更精确的方法。三分法适用于导数复杂、不存在或难以求解的情况例如f(x)本身就是一个黑盒模拟过程。vs. 模拟退火/爬山算法对于多峰函数或复杂搜索空间三分法会失败而模拟退火等随机优化算法有可能找到全局最优解但代价是不保证最优性且运行时间不确定。三分法在适用范围内是确定性的、高效的。6. 从三分到更一般的凸函数优化三分法解决的是一维单峰函数凸函数或凹函数的极值问题。这是凸优化中最简单的特例。理解三分法是迈向更广泛优化问题求解的第一步。凸函数Convex Function有一个优美的性质其局部极小值就是全局极小值。三分法本质上是在利用凸函数的“碗状”性质。对于高维凸函数我们有梯度下降、牛顿法等更强大的工具。但在一维情况下三分法以其实现简单、无需导数、鲁棒性强的特点占据了一席之地。在实际编程中当你遇到一个求最优解的问题并且决策变量只有一个连续参数时思考顺序应该是能否写出目标函数f(x)f(x)在搜索区间上是否看起来是单峰的凸的或凹的可以通过端点趋势、物理意义或简单求导判断。如果答案是肯定的那么三分法就是你工具箱里的首选武器。最后记住三分法的核心口诀取两点判高低弃外侧缩区间至精度。将这个流程内化再结合对问题本身的深刻理解你就能将许多看似复杂的最优化问题优雅地转化为几次函数求值和比较。