C++三分查找怎么求凸函数极值-C++-PHP中文网

三分查找适用于单峰函数，即先单调增后单调减（上凸）或先减后增（下凸）的连续函数，如二次函数 -x²+4x、绝对值和函数等；必须人工保证区间内单峰性，否则结果错误。

c++三分查找怎么求凸函数极值

三分查找适用的凸函数长什么样

三分查找只适用于严格单峰函数，也就是先单调增再单调减（上凸）或先减后增（下凸）的连续函数。C++ 中没法自动判断函数是否凸，必须由你保证 f(x) 在给定区间 [l, r] 上是单峰的——否则结果不可靠，甚至完全错误。

常见可直接用三分的场景：二次函数（如 -x*x + 4*x）、带绝对值的和（如 abs(x-1) + abs(x-3) + abs(x-5)）、某些几何距离和、简单多项式拟合目标函数。

容易踩的坑：
• 把非单峰函数（比如有多个局部极值的 sin(x) + 0.1*x 在大区间上）硬套三分，结果停在某个局部极值点
• 区间端点选得太大，导致浮点精度丢失或迭代不收敛
• 忘记检查函数定义域，f(x) 在中间某点崩溃（如除零、越界访问）

标准三分模板怎么写（double 精度版）

核心逻辑是不断缩小区间，保留包含极值的那一段。对上凸函数（求最大值），保留 f(m1) 的那一侧；下凸函数（求最小值）则反过来。实际中多数人直接按「求最大值」写，需要最小值时把目标函数取负即可。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

double ternary_search(double l, double r, int iter = 100) {
    while (iter--) {
        double m1 = l + (r - l) / 3.0;
        double m2 = r - (r - l) / 3.0;
        if (f(m1) <p>说明：<br>
• 迭代次数 <code>iter = 100</code> 比固定精度（如 <code>r-l ）更稳，避免浮点震荡<br>
• <code>m1</code> 和 <code>m2</code> 必须严格在 <code>(l, r)</code> 内，不能写成 <code>l + (r-l)/2</code> 或错位计算<br>
• 函数 <code>f</code> 必须是捕获上下文的 lambda 或全局/静态函数，不能带未绑定的 this 指针（类成员函数需包装）</code></p><h3>整数域三分要注意什么</h3><p>当自变量必须是整数（比如数组下标、离散决策点），不能直接用浮点三分。此时要改用整数三分，终止条件是 <code>r - l ，最后暴力检查剩余 2–3 个点。</code></p><pre class="brush:php;toolbar:false;">int ternary_search_int(int l, int r) {
    while (r - l > 2) {
        int m1 = l + (r - l) / 3;
        int m2 = r - (r - l) / 3;
        if (f(m1)  f(res)) res = i;
    }
    return res;
}

关键点：
• m1 和 m2 用整数除法，但要确保 m1 （当 <code>r-l 时可能相等，所以必须加循环终止条件）<br> • 不要试图用 <code>while (l + 四舍五入逼近，整数三分没有“中间点唯一性”，必须收尾暴力<br> • 如果函数在整数点不满足严格单峰（比如平台段），三分只能返回其中一个极值位置，无法区分多个解