什么是三分查找算法三分查找Ternary Search是一种用于在单峰函数Unimodal Function上寻找极值最大值或最小值的算法。与二分查找适用于单调函数不同三分查找适用于函数值先严格递增后严格递减或先严格递减后严格递增的情况。算法原理对于一个在区间 [l, r] 上单峰的函数 f(x)三分查找的基本思想是每次将搜索区间分为三等份通过比较两个中间点的函数值舍弃不可能包含极值点的那部分区间从而逐步缩小搜索范围。具体步骤计算两个中间点mid1 l (r - l) / 3mid2 r - (r - l) / 3比较 f(mid1) 和 f(mid2)求最大值时若 f(mid1) f(mid2)则极值点可能在 [mid1, r] 区间令 l mid1否则极值点可能在 [l, mid2] 区间令 r mid2求最小值时若 f(mid1) f(mid2)则极值点可能在 [l, mid2] 区间令 r mid2否则极值点可能在 [mid1, r] 区间令 l mid1重复上述步骤直到区间长度小于预设精度 eps。单峰函数的定义与判定要正确应用三分查找首先需要理解什么是单峰函数。单峰函数是指在定义域内存在唯一极值点最大值或最小值的函数函数值在极值点的一侧严格单调递增在另一侧严格单调递减。数学定义设函数 f(x) 在区间 [a, b] 上定义。若存在点 c ∈ [a, b]使得在区间 [a, c] 上f(x) 严格单调递增或递减在区间 [c, b] 上f(x) 严格单调递减或递增则称 f(x) 在 [a, b] 上是单峰函数c 为极值点。常见单峰函数示例二次函数f(x) ax² bx ca ≠ 0绝对值函数f(x) |x - a| b指数衰减函数f(x) e^{-|x-a|} b某些三角函数如 f(x) sin(x) 在 [0, π] 区间内是单峰的单峰性验证方法数学分析通过求导判断函数的单调性数值验证在区间内采样多个点观察函数值变化趋势问题背景根据实际问题的物理意义或几何意义判断C 实现示例1. 求单峰函数最大值#include iostream #include cmath using namespace std; // 示例函数f(x) -(x-3)^2 5在 x3 处取得最大值 5 double f(double x) { return -(x - 3) * (x - 3) 5; } // 三分查找求函数最大值 double ternary_search_max(double l, double r, double eps) { while (r - l eps) { double mid1 l (r - l) / 3; double mid2 r - (r - l) / 3; if (f(mid1) f(mid2)) { l mid1; // 最大值在 [mid1, r] } else { r mid2; // 最大值在 [l, mid2] } } return (l r) / 2; // 返回极值点横坐标 } int main() { double l 0, r 6, eps 1e-6; double x_opt ternary_search_max(l, r, eps); cout 最大值点 x ≈ x_opt endl; cout 最大值 f(x) ≈ f(x_opt) endl; return 0; }2. 求单峰函数最小值#include iostream #include cmath using namespace std; // 示例函数f(x) (x-2)^2 1在 x2 处取得最小值 1 double g(double x) { return (x - 2) * (x - 2) 1; } // 三分查找求函数最小值 double ternary_search_min(double l, double r, double eps) { while (r - l eps) { double mid1 l (r - l) / 3; double mid2 r - (r - l) / 3; if (g(mid1) g(mid2)) { r mid2; // 最小值在 [l, mid2] } else { l mid1; // 最小值在 [mid1, r] } } return (l r) / 2; } int main() { double l -5, r 5, eps 1e-6; double x_opt ternary_search_min(l, r, eps); cout 最小值点 x ≈ x_opt endl; cout 最小值 g(x) ≈ g(x_opt) endl; return 0; }3. 通用三分查找模板#include iostream #include cmath #include functional using namespace std; // 通用三分查找模板 // func: 单峰函数 // l, r: 搜索区间 // eps: 精度 // find_max: true 表示求最大值false 表示求最小值 double ternary_search(functiondouble(double) func, double l, double r, double eps, bool find_max) { while (r - l eps) { double mid1 l (r - l) / 3; double mid2 r - (r - l) / 3; double f1 func(mid1); double f2 func(mid2); if (find_max) { // 求最大值 if (f1 f2) { l mid1; // 最大值在 [mid1, r] } else { r mid2; // 最大值在 [l, mid2] } } else { // 求最小值 if (f1 f2) { r mid2; // 最小值在 [l, mid2] } else { l mid1; // 最小值在 [mid1, r] } } } return (l r) / 2; } // 示例函数1抛物线 double parabola(double x) { return -(x - 4) * (x - 4) 10; } // 示例函数2绝对值函数 double abs_func(double x) { return abs(x - 3) 2; } int main() { // 示例1求抛物线最大值 double x1 ternary_search(parabola, 0, 8, 1e-6, true); cout 抛物线最大值点: x1 , 最大值: parabola(x1) endl; // 示例2求绝对值函数最小值 double x2 ternary_search(abs_func, -5, 10, 1e-6, false); cout 绝对值函数最小值点: x2 , 最小值: abs_func(x2) endl; return 0; }算法复杂度分析三分查找的时间复杂度为 O(log3 n)其中 n 为初始区间长度与精度的比值。每次迭代将搜索区间缩小为原来的 2/3因此迭代次数约为 log3/2(n/eps)。详细推导设初始区间长度为 L精度要求为 ε。每次迭代后区间长度变为原来的 2/3。经过 k 次迭代后区间长度变为Lk L × (2/3)k当 Lk ≤ ε 时停止迭代即L × (2/3)k ≤ ε解得k ≥ log3/2(L/ε)因此三分查找的时间复杂度为 O(log(L/ε))与二分查找的 O(log(L/ε)) 同阶但常数因子略大。空间复杂度三分查找只需要常数级别的额外空间几个变量因此空间复杂度为 O(1)。应用场景凸函数/凹函数极值求解如抛物线、绝对值函数等优化问题寻找最佳参数、最优配置计算几何点到凸多边形/凸包的最远/最近距离算法竞赛常见于需要寻找单峰函数极值的题目实际应用案例1. 最优定价问题假设某商品的需求函数为 D(p) 1000 - 50p成本函数为 C(p) 200 10p利润函数为 π(p) p × D(p) - C(p)。利润函数通常是单峰的可以通过三分查找找到最优定价。2. 最短路径问题在某些几何问题中如寻找点到线段的最短距离距离函数关于某个参数是单峰的可以使用三分查找快速找到最小值。3. 机器学习参数调优在某些简单的机器学习模型中损失函数关于某个超参数可能是单峰的可以使用三分查找寻找最优超参数。三分查找的变体与优化1. 黄金分割三分法传统三分法每次需要计算两个中间点的函数值即两次函数求值。黄金分割三分法通过选择特殊的比例黄金分割比使得每次迭代只需要计算一个新的函数值从而减少计算量。2. 整数三分查找当定义域为整数时需要对算法进行适当调整// 整数三分查找求最大值 int ternary_search_int_max(int l, int r) { while (r - l 2) { // 区间长度大于2时继续 int mid1 l (r - l) / 3; int mid2 r - (r - l) / 3; if (f(mid1) f(mid2)) { l mid1; } else { r mid2; } } // 在剩余的小区间内线性查找 int best l; for (int i l 1; i r; i) { if (f(i) f(best)) best i; } return best; }3. 自适应三分查找当函数计算代价很高时可以使用自适应三分查找根据函数值的变化趋势动态调整搜索策略减少不必要的函数求值。注意事项单峰性验证必须确保函数在搜索区间内是严格单峰的精度控制eps 的选择需要根据问题要求平衡精度与效率整数三分当定义域为整数时循环条件可改为 while (r - l 2)与二分的区别二分查找适用于单调函数寻找特定值三分查找适用于单峰函数寻找极值收敛条件循环终止条件通常为区间长度小于预设精度但也要考虑最大迭代次数避免无限循环数值稳定性对于浮点数运算要注意精度误差的累积常见错误与调试技巧常见错误函数非单峰在非单峰区间使用三分查找会导致错误结果精度设置不当精度过高导致迭代次数过多精度过低导致结果不准确边界条件处理不当特别是整数三分时区间边界处理容易出错浮点数比较问题直接使用 比较浮点数可能导致无限循环调试技巧可视化函数图像绘制函数图像直观判断单峰性打印中间结果在循环中打印 l, r, mid1, mid2 和对应的函数值单元测试编写测试用例验证算法在各种情况下的正确性对比验证与暴力枚举结果对比验证算法正确性三分查找与二分查找的对比特性二分查找三分查找适用函数单调函数单峰函数目标寻找特定值寻找极值最大/最小值每次迭代比较次数1次2次区间缩小比例1/22/3时间复杂度O(log n)O(log n)空间复杂度O(1)O(1)常见应用有序数组查找、方程求根优化问题、几何问题总结三分查找是解决单峰函数极值问题的高效算法通过每次将搜索区间三等分并比较两个中间点的函数值可以快速收敛到极值点。掌握三分查找的原理和实现能够帮助我们在算法竞赛和实际编程中解决一类重要的优化问题。关键要点总结三分查找适用于单峰函数通过比较两个三等分点的函数值来缩小搜索区间算法时间复杂度为 O(log n)与二分查找同阶但常数因子略大实现时需要注意单峰性验证、精度控制和边界条件处理整数三分需要特殊处理通常将循环条件改为 w
