C++ 三分查找算法解析
什么是三分查找算法三分查找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

相关新闻

如何控制antdesign组件中的选择器组件输入框指定标签不可删除

如何控制antdesign组件中的选择器组件输入框指定标签不可删除

<a-select v-model:value="orderRecord.selectedActionIds" mode="multiple" placeholder="请选择配送动作" style="width: 100%" :options="getFilteredActionOptions(orderRecord)"@change="(values) => handl…

2026/11/22 3:55:19 阅读更多 →
薄膜开关多层结构设计与电路布局优化

薄膜开关多层结构设计与电路布局优化

薄膜开关看似结构简单&#xff0c;实际上是一个多层复合的功能体系。每一层的材料选择、几何参数、加工工艺都会对最终产品的性能产生影响。本文从结构设计和电路布局两个技术维度进行深入分析&#xff0c;探讨薄膜开关设计中的关键技术决策点。一、多层结构的力学与电气协同设…

2026/11/18 19:44:41 阅读更多 →
CUDA 错误检查:cudaGetLastError + cudaDeviceSynchronize

CUDA 错误检查:cudaGetLastError + cudaDeviceSynchronize

新手最容易踩的坑集中营 一、为什么这一节格外重要,很多新手不当回事 CUDA代码写错了,很多时候不会像CPU代码那样直接崩溃报错, 而是"看起来正常跑完了,但结果不对",或者干脆"什么都没发生, 数组里全是初始值"。原因和前面已经学过的两个特性直接相…

2026/11/20 11:35:52 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年&#xff0c;我大部分时间都在跟浏览器标签页打交道&#xff0c;直到第一次把桌面应用跑起来&#xff0c;才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词&#xff0c;最开始是在某段时间频繁出现在同事的讨论里&#xff0c;一个用HTML…

2026/11/21 23:27:35 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档&#xff0c;主要面向智能锁安装人员、终端用户及售后维护者&#xff0c;帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件&#xff0c;大小4.37MB&#xff0c;内容结构清晰&#xff…

2026/11/21 23:27:35 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统&#xff0c;整车要求空载跑到8m/s&#xff0c;电机转速已经拉到额定点&#xff0c;驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令&#xff0c;转速纹丝不动&#xff0c;三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/21 23:27:35 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年&#xff0c;用它写过嵌入式驱动、做过游戏服务端&#xff0c;也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词&#xff0c;我其实挺感慨的——这门语言的难点从来不是语法多&#xff0c;而是知识点之间的耦合太深…

2026/11/21 23:27:35 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书以PDF格式发布&#xff0c;适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开&#xff0c;先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能&#xff0c;再给出完整安装步骤&…

2026/11/21 23:27:36 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历&#xff1a;翻开源码注释、论文摘要或者一份专业报告&#xff0c;每个字都认识&#xff0c;连在一起却像天书。想找人聊聊&#xff0c;身边要么没人懂&#xff0c;要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型&#xff0c;几秒钟之后&a…

2026/11/21 23:27:37 阅读更多 →

日新闻

周新闻

月新闻