从二分到三分：单峰函数极值搜索算法原理与C++实现

1. 从二分到三分算法思想的一次自然延伸在算法学习的路上二分查找Binary Search几乎是所有人的第一道坎也是理解“分治”与“减治”思想的绝佳起点。它的核心逻辑清晰得近乎优雅在一个单调有序的序列中通过不断与中间值比较将搜索范围对半砍掉从而以对数级的时间复杂度逼近答案。我们用它找数组中的特定元素解方程甚至在答案具有单调性时求解最优值问题即二分答案法。但不知道你有没有想过这样一个问题如果目标函数不是单调的而是一个先增后减或先减后增的“单峰函数”我们该如何高效地找到那个顶峰最大值或谷底最小值呢这就是三分法Ternary Search登场的时刻。你可以把它看作是二分法在处理凸函数极值问题时的一个“表亲”。二分法依赖单调性通过比较中点与目标值的关系决定舍弃左半还是右半。而三分法则适用于寻找单峰函数Unimodal Function的极值点。所谓单峰就是在定义域[l, r]内函数值先严格单调上升到峰值然后严格单调下降或先下降后上升。峰值点或谷值点只有一个。三分法的聪明之处在于它不像二分法那样只取一个中点而是取两个点m1 l (r - l) / 3和m2 r - (r - l) / 3。通过比较f(m1)和f(m2)的大小我们就能判断峰值点更可能位于哪三分之一区间从而安全地舍弃掉另外三分之一。举个例子想象你在爬一座形状规则的山只有一个山顶你站在山脚l对面山脚是r。你不知道山顶在哪但你能感知海拔函数值。你向前走三分之一路程到m1再向后走三分之一路程到m2从r往回走。如果你发现m1的海拔比m2高那说明山顶更可能在你和m2之间吗不恰恰相反。因为函数是单峰的如果f(m1) f(m2)意味着m2点已经处在了下降的坡面上那么峰值点山顶必然在m1的左侧即区间[l, m2]。因为如果峰值在m2右侧那么从峰值到m2应该是下降的但m1在m2左侧且值更高这与单峰性矛盾。因此我们可以安全地将搜索范围从[l, r]缩小到[l, m2]。同理如果f(m1) f(m2)则峰值在[m1, r]如果相等则峰值就在[m1, m2]之间通常我们可以任意舍弃一边。理解了这个核心思想你就能明白三分法解决的是二分法无能为力的一类问题在连续或离散的单峰函数上寻找极值点。它在竞赛编程、数值计算和机器学习参数调优中都有应用。接下来我们将深入C实现的三分法从最基础的实数域求凸函数极值到离散整数域上的应用再到与二分答案法的对比与结合最后探讨其局限性和常见“坑点”。2. 核心原理与C实现框架2.1 算法流程与收敛性分析三分法的算法流程非常规整其正确性完全建立在函数的单峰性假设之上。假设我们要求单峰函数f(x)在区间[l, r]上的最大值点求最小值逻辑对称。以下是标准步骤确定精度或迭代次数给定一个足够小的精度要求eps例如1e-7或者一个最大迭代次数例如对while循环设置100次。计算三等分点在每次迭代中计算两个中间点m1 l (r - l) / 3.0m2 r - (r - l) / 3.0注意这里使用(r - l) / 3.0而不是(r - l) * 1.0 / 3是为了避免整数运算带来的精度问题。关键是要保证m1 m2。比较函数值并缩小区间如果f(m1) f(m2)那么最大值点不可能在m1左边。因为如果最大值点在l和m1之间由于函数在峰值左侧单调增应该有f(m1) f(m2)与条件矛盾。因此我们可以将左端点更新为l m1。如果f(m1) f(m2)同理最大值点不可能在m2右边因此将右端点更新为r m2。如果f(m1) f(m2)在浮点数计算中很少严格相等通常发生在峰值平台区理论上峰值位于[m1, m2]之间我们可以同时更新l m1和r m2或者任选上述一种策略。实践中由于浮点误差我们通常只使用前两种判断。检查终止条件当区间长度r - l小于预设精度eps时终止循环。此时(l r) / 2.0或l、r均可作为极值点坐标的近似值。关于收敛性每次迭代区间长度大约缩短为原来的2/3。假设初始区间长度为L经过k次迭代后区间长度约为L * (2/3)^k。要达到精度eps需要的迭代次数k满足(2/3)^k * L eps解得k log(eps / L) / log(2/3)。由于log(2/3)是负数这个式子是有意义的。例如L1000,eps1e-7大约需要log(1e-10) / log(2/3) ≈ (-23) / (-0.405) ≈ 57次迭代。这比二分法的收敛速度每次区间减半要慢一些但对于单峰函数极值问题这是最优的基于函数值比较的确定性算法之一。注意一个常见的误解是认为三分法可以处理多峰函数。绝对不行。如果函数有多个局部极值比较f(m1)和f(m2)无法判断全局极值的位置算法会错误地收敛到某个局部极值点或者根本失效。确保单峰性是使用三分法的前提。2.2 浮点数三分模板代码与细节下面是一个经典的C浮点数三分求函数最小值的模板。我们以求f(x) x^2 - 6x 10在[0, 10]上的最小值为例。这是一个开口向上的抛物线最小点在x3。#include iostream #include cmath #include iomanip using namespace std; // 目标函数这里是一个简单的二次函数 double f(double x) { return x * x - 6 * x 10; // 最小值为1在x3处取得 } // 三分法求函数最小值 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 (f(m1) f(m2)) { // 最小值在左侧区间 [l, m2] r m2; } else { // 最小值在右侧区间 [m1, r] l m1; } } // 循环结束时l和r非常接近任取其一或取平均作为近似最小值点 return (l r) / 2.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 (f(m1) f(m2)) { // 注意符号与求最小值相反 r m2; } else { l m1; } } return (l r) / 2.0; } int main() { double l 0.0, r 10.0; double min_point ternary_search_min(l, r); cout fixed setprecision(10); cout 最小值点 x ≈ min_point endl; cout 最小值 f(x) ≈ f(min_point) endl; // 对于这个开口向上的函数求最大值在边界 double max_point ternary_search_max(l, r); cout 最大值点 x ≈ max_point endl; // 应为0或10 cout 最大值 f(x) ≈ f(max_point) endl; return 0; }关键细节与陷阱精度eps的选择eps并非越小越好。它需要与目标函数的自变量变化尺度以及函数值计算精度相匹配。如果eps设置得比浮点数精度std::numeric_limitsdouble::epsilon()约2.22e-16还小循环可能因浮点误差无法终止或陷入无限循环。通常1e-9到1e-12对于大多数问题足够了。对于答案可能是整数的问题可以设置eps1e-7然后对结果四舍五入到整数。循环条件务必使用while (r - l eps)而不是while (l r)。因为浮点数比较存在误差l可能永远无法精确等于r。三等分点的计算强烈建议使用m1 l (r - l) / 3.0和m2 r - (r - l) / 3.0。这比m1 (2*l r) / 3.0和m2 (l 2*r) / 3.0在数值上更稳定尤其是在l和r绝对值很大时能减少舍入误差。函数调用开销在循环内f(m1)和f(m2)通常会被计算两次。如果f(x)计算非常耗时例如涉及复杂模拟或数据库查询这会成为性能瓶颈。一个优化技巧是缓存函数值但在这个简单模板中清晰性优先。2.3 整数域上的三分法当自变量是整数或者函数定义在离散的整数点上时我们同样可以使用三分法的思想但循环终止条件需要调整。因为区间长度是整数我们无法也无必要缩放到无限小。整数三分的典型写法是通过迭代次数控制或者当区间长度小于3时直接暴力枚举。假设我们在整数区间[L, R]上寻找单峰函数的最大值函数f(int x)。方法一固定迭代次数由于每次迭代区间长度至少减少1/3对于一个长度为N的区间大约需要O(log_{1.5} N)次迭代。我们可以直接循环一个足够多的次数比如100次这对于N在int范围内绰绰有余。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; // 峰值在[m1, R] } else { R m2; // 峰值在[L, m2] } } // 区间长度3暴力比较 int ans f(L), pos L; for (int i L 1; i R; i) { int val f(i); if (val ans) { // 找最大值 ans val; pos i; } } return pos; // 返回最大值点 }方法二缩小到小范围后暴力这是更常见的写法。循环条件设为R - L 3保证区间内至少有两个中间点m1和m2。退出循环后区间内最多剩下3个点L, L1, L2直接比较即可。实操心得整数三分中m1和m2的计算使用整数除法。由于(R - L) / 3会向下取整可能导致m1 m2当R-L 3时。这就是为什么循环条件要设为R - L 2确保m1和m2是两个不同的点才能进行比较。如果出现m1 m2算法就无法判断该舍弃哪边了。3. 典型应用场景与问题剖析三分法不是一种每天都会用到的算法但一旦遇到它擅长的问题它就是最直接高效的武器。下面通过几个典型场景和洛谷上的经典题目来具体感受它的应用。3.1 场景一单峰函数求极值这是三分法最直接的应用。题目通常会直接或间接地给出一个关于某个变量的单峰函数要求你找出极值点。关键在于识别出函数的单峰性。例题P3382 【模板】三分法洛谷这是三分法的标准模板题。题目直接给出一个N次多项式函数F(x)并明确告知在区间[l, r]上是单峰的要求求出峰值点坐标。这就是对上述浮点数三分模板的直接应用。你只需要读入系数实现F(x)的计算然后套用模板即可。这道题的价值在于验证你的三分实现是否正确特别是浮点数精度处理。例题寻找函数最小值自定义假设一个问题你要在一条笔直的海岸线上建一个码头海岸线上有N个仓库位置已知。码头建在海岸线上某一点运输成本与仓库到码头距离的平方成正比。求使总运输成本最小的码头位置。 设码头位置为x第i个仓库位置为a[i]则总成本f(x) Σ (x - a[i])^2。这是一个关于x的二次函数Σ x^2 - 2Σ a[i] * x Σ a[i]^2其二次项系数N 0所以是开口向上的抛物线有唯一最小值点。这个最小值点实际上就是仓库位置的算术平均数x (Σ a[i]) / N。我们可以用三分法来求解虽然用公式直接算更简单但这验证了对于凸二次函数三分法能正确找到极值点。3.2 场景二距离函数的最大值最小化或最小值最大化这是一类非常经典的问题也称为“最小最大问题”或“最大最小问题”。通常描述为在某种方案下定义一种“代价”或“距离”我们要在最坏情况下最大距离尽可能好最小化这个最大距离或者在最好情况下最小收益尽可能有保障最大化这个最小收益。当这个“最坏代价”关于决策变量是单峰函数时就可以用三分法。经典模型一条直线上有N个点选一个点使得该点到所有点的最大距离最小。这就是最小覆盖半径问题。设选的点为x定义函数f(x) max(|x - a[i]|)即x到所有点的最远距离。我们需要最小化f(x)。 可以证明或直觉感受f(x)是一个先减后增的单峰函数更准确地说是一个凸函数V形。当x在最左点左边时最远距离是到最右点且随x右移而减小当x超过某个位置后最远距离变成到最左点且随x右移而增大。最小值点就在最左点和最右点的中点附近。因此我们可以对x进行三分求f(x)的最小值。例题P2571 [SCOI2010] 传送带洛谷这道题是三分法应用的经典。题目描述在平面上有两条线段AB和CD你可以在AB上以速度P移动在CD上以速度Q移动在平面上其他区域以速度R移动。求从A点出发经过AB上一点X再经过CD上一点Y最后到达D点的最短时间。 设X是AB上的点Y是CD上的点。总时间T是关于X和Y两个变量的函数。一个关键的洞察是当X固定时T是关于Y的单峰函数凸函数反之当Y固定时T是关于X的单峰函数。这允许我们使用三分套三分的方法先在外层三分X的位置对于每一个固定的X在内层用三分法求出最优的Y从而得到该X下的最短时间。最终外层三分找到最优的X。这是三分法处理多变量问题的一种方式要求函数关于每个变量单独满足单峰性。3.3 场景三与二分答案法结合二分答案法要求答案具有单调性即对于一个猜测的答案mid我们能判断“是否存在一种方案使得指标值至少或至多为mid”并且这个判断函数check(mid)的返回值关于mid是单调的通常是从True变False或反之。有时候我们遇到的问题的“可行性”关于某个参数不是单调的而是单峰的。这时三分法就可以替代二分法。举例分配资源使得最小收益最大化。假设有M个任务和N个资源单位每个任务消耗一定资源并产生收益。我们要将资源分配给任务目标是最大化所有任务中收益最小的那个即让最差的任务也尽量好。设我们设定的最小收益目标是T那么问题转化为是否存在一种分配方案使得每个任务的收益都至少为T这个check(T)函数判断可行性关于T通常是单调的如果T很小很容易实现T很大就无法实现。所以这是二分答案。现在考虑一个变种目标不是最大化最小收益而是最大化总收益关于某个分配参数x的函数并且这个总收益函数g(x)是单峰的。例如x代表投资激进程度太保守则收益低太冒险则可能亏损中间有个最优值。这时最优的x就可以通过三分法求得。check(x)在这里不是返回布尔值而是直接计算g(x)的值。区分何时用二分何时用三分二分答案用于求解满足某种条件的最大/最小值。关键在于存在一个单调的判定函数check(ans)。例如“最大的最小距离”、“最小的最大重量”这类问题check(mid)通常是“能否做到距离mid”或“能否承受重量mid”答案具有单调性。三分法用于直接求解一个单峰函数的极值点。没有“是否可行”的判定而是直接计算函数值进行比较。目标就是找到使得f(x)最大或最小的x。有些问题既可以用三分也可以用二分答案判定但思路不同。例如前述的“最小覆盖半径”可以用三分法直接求f(x)的最小值也可以用二分答案法猜半径R判定是否存在一个点距离所有点都不超过R这是一个覆盖问题判定函数是单调的。4. 实现技巧、调试与常见问题4.1 避免浮点数误差的实用技巧浮点数三分中误差主要来自两个方面一是循环终止条件二是函数值比较。以下技巧可以帮助你写出更鲁棒的代码设置合理的迭代次数上限除了用while (r - l eps)可以再加一个计数器防止因特殊函数或精度问题导致无限循环。int iter 0; while (r - l eps iter 100) { // ... 三分逻辑 iter; }谨慎比较浮点数避免直接使用比较f(m1)和f(m2)。由于浮点误差两个理论上相等的数可能略有不同。通常使用和就够了。如果一定要处理相等情况可以用fabs(f(m1)-f(m2)) 1e-12来判断。最终答案的处理循环结束后l和r非常接近。通常取(lr)/2作为最终答案。如果题目要求输出函数值最好用这个中点坐标重新计算一次f(x)而不是用最后一次迭代的f(m1)或f(m2)因为中点坐标更稳定。精度与数据范围的平衡如果自变量范围很大如[0, 1e9]而精度要求很高如1e-12可能需要将eps设置得比1e-12稍大比如1e-10或者增加迭代次数。因为当区间长度很大时浮点数的相对误差可能会影响m1和m2的计算。4.2 验证单峰性三分法正确性的前提三分法最危险的陷阱就是误用在非单峰函数上。如何验证单峰性数学推导对于连续函数可以求二阶导数。如果在定义域内二阶导数恒大于等于0是下凸函数有最小值恒小于等于0是上凸函数有最大值。对于离散函数可以分析差分相邻项的差的变化趋势。观察与直觉很多问题具有对称性或物理意义极值点唯一。例如距离的平方和、时间关于路径点的函数如传送带问题通常是凸的。画图辅助对于简单函数或小规模数据可以编程输出一系列点的函数值观察其变化趋势。这是调试时最有效的方法。警惕平台区域如果函数有一段是平坦的导数等于0严格来说不是“单峰”先严格增后严格减。但三分法通常仍然有效因为f(m1)f(m2)时我们无论舍弃哪边极值点都还在剩下的区间里。不过收敛到平台上的具体哪一点就不确定了。4.3 三分法常见问题排查表问题现象可能原因解决方案程序陷入死循环1. 浮点数精度eps设置过小r-l始终大于eps。2. 整数三分循环条件写错导致m1m2且无法缩小区间。3. 函数f(x)在区间内非单峰算法在局部震荡。1. 增加迭代次数上限或适当调大eps。2. 检查整数三分循环条件确保R-L3。3. 重新审视问题验证函数单峰性。输出中间值观察区间变化。结果精度不够1.eps设置过大。2. 迭代次数不足。3. 函数值计算本身有较大误差如涉及大量浮点运算。1. 根据题目要求精度适当减小eps如1e-9。2. 改用固定迭代次数如100次确保区间足够小。3. 使用long double提高计算精度或优化f(x)的计算顺序减少误差。答案明显错误1. 求最大/最小值时if条件判断符号写反。2. 区间初始值[l, r]设置错误没有包含真正的极值点。3. 函数f(x)实现有bug。1. 牢记口诀求最小值时f(m1) f(m2)则舍去右边(rm2)。可以画一个“V”形图辅助记忆。2. 确保初始区间足够宽能覆盖所有可能的最优解。有时需要根据问题背景估算范围。3. 单独测试f(x)函数用几个已知点验证。整数三分找不到正确整数解循环结束后在[L, R]区间暴力查找时漏掉了边界点或比较逻辑有误。确保暴力查找的循环是for (int i L; i R; i)并且正确初始化ans和pos。4.4 三分法与其他搜索算法的对比与二分查找对比二分适用于单调序列中查找特定值或单调判定函数下的最优解二分答案。三分适用于单峰凸函数上查找极值点。核心区别二分每次比较的是中点值与目标值的关系三分比较的是两个三等分点的函数值关系。与黄金分割搜索对比黄金分割搜索Golden-section search也是一种寻找单峰函数极值的方法。它通过黄金比例约0.618分割区间每次迭代只需要计算一个新的函数值因为另一个点可以复用上一轮的值理论上比三分法每次计算两个新点效率稍高。但三分法逻辑更简单直观代码易于理解和记忆在大多数编程竞赛和日常应用中其性能差异可以忽略不计。三分法是更通用的选择。与梯度下降等数值方法对比对于高维、非凸、复杂的函数三分法不适用。此时需要梯度下降、牛顿法等数值优化方法。三分法的优势在于对于一维单峰函数它是确定性且收敛性有保证的算法不需要计算导数对函数要求低只需能求值。5. 综合实战从问题识别到代码实现让我们通过一个综合性的例子走完从问题分析、识别算法到代码实现和调试的全过程。问题描述自定义 你正在设计一个无线网络基站。在一条笔直的道路上看作x轴有N个用户第i个用户的位置是a[i]。你可以在道路上任意位置x放置一个基站。基站的信号强度随距离衰减对于距离基站d的用户接收到的信号质量为Q P / (1 d^2)其中P是基站的发射功率常数。为了保证所有用户都能正常通信我们需要让信号质量最差的那个用户的信号质量尽可能高。即选择x最大化min_{i1 to N} (P / (1 (x - a[i])^2))。 由于P是常数这等价于最小化max_{i1 to N} (1 (x - a[i])^2)也就是最小化x到所有用户的最大距离的平方再加1。进一步也就是最小化x到所有用户的最大距离。设f(x) max |x - a[i]|。第一步识别算法问题转化为求一个点x使得它到N个已知点的最大距离最小。这正是前面提到的“最小覆盖半径”问题。我们需要证明或确信f(x)是单峰的。当x远小于所有a[i]时f(x) max(a[i]) - x随x增大而减小。当x远大于所有a[i]时f(x) x - min(a[i])随x增大而增大。当x在中间时f(x)是分段线性函数其图像是一个“V”形由多个绝对值函数取最大值构成这是一个凸函数单峰函数。因此可以使用三分法求其最小值点。第二步确定搜索区间显然最优的x一定位于所有用户位置的最小值min_a和最大值max_a之间。我们可以将初始区间设为[min_a, max_a]。为了保险甚至可以设得更宽一些比如[min_a - 1, max_a 1]。第三步实现函数f(x)double max_distance(double x, const vectordouble positions) { double max_dist 0.0; for (double pos : positions) { max_dist max(max_dist, fabs(x - pos)); } return max_dist; // f(x) }第四步套用三分法模板求最小值double ternary_search_min_f(const vectordouble pos) { double l *min_element(pos.begin(), pos.end()) - 1.0; // 左边界 double r *max_element(pos.begin(), pos.end()) 1.0; // 右边界 const double eps 1e-7; while (r - l eps) { double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (max_distance(m1, pos) max_distance(m2, pos)) { r m2; // 最小值在[l, m2] } else { l m1; // 最小值在[m1, r] } } return (l r) / 2.0; }第五步分析结果与验证得到最优的x_opt后可以计算f(x_opt)这就是最小的最大覆盖半径。有趣的是对于这个问题最优解x_opt其实就是(min_a max_a) / 2即最左和最右用户的中点。因为要使最大距离最小基站放在两端点的中点上这样到两端的距离相等且任何其他点都会导致到某一端的距离更大。我们的三分法应该能验证这个结果。第六步扩展思考如果用户不是分布在直线上而是在平面上问题就变成了“最小圆覆盖”无法用简单的一维三分法解决需要更复杂的几何算法如Welzl算法。这提醒我们三分法的应用前提是问题可以转化为关于单个变量的一维单峰函数优化。通过这个完整的例子你应该对三分法如何解决一个实际问题有了清晰的认识。核心步骤永远是1) 定义目标函数2) 证明或论证其单峰性3) 确定搜索范围4) 实现函数求值5) 套用三分模板6) 分析结果。掌握了这个流程你就能在面对“求最优...”、“最大化...”、“最小化...”这类问题时多一种强有力的思路和工具。