140-杂项-三分搜索

核心概述

三分搜索用于单峰（凸/凹或先增后减）的一维函数极值定位，每轮评估两内点并舍弃约 1/3 区间，可在连续域与整数域内以对数轮次收敛到极值。

原文引述

Description: Ternary search on unimodal f over an interval; evaluate at two interior points and shrink to the better side. Works for real (with eps) and integer (discrete) domains.（摘自本节点现有英文注释） Time: O(log((R-L)/ε)) for real; O(log N) for integer domain（摘自本节点现有英文注释） Status: tested（摘自本节点现有英文注释）

展开阐述

• 适用条件与目标

  • 单峰性：存在唯一极大/极小点，且两侧单调。
  • 域类型：连续/离散均可；连续域以精度 ε 收敛，整数域以小范围线性收尾。
  • 目标：极大化或极小化（最小化可对 f 取相反数）。

• 核心流程

  • 连续区间 [l, r]：
    • 取 m1 = l + (r−l)/3, m2 = r − (r−l)/3。
    • 若 f(m1) < f(m2)，则极值在 [m1, r]；否则在 [l, m2]。
    • 迭代至 r−l < ε，返回中点或当前更优点。
  • 整数区间 [l, r]：
    • while r−l > 3：同上更新边界。
    • 对收尾小段逐点枚举取最优。

• 代码框架（连续实数极大值）

// 目标函数应满足单峰性
double ternary_search_double(double l, double r, double eps = 1e-9) {
    auto f = [](double x) { /* TODO: 定义 f(x) */ return -x*x + 3*x + 1; };
    while (r - l > eps) {
        double m1 = l + (r - l) / 3.0;
        double m2 = r - (r - l) / 3.0;
        if (f(m1) < f(m2)) l = m1; else r = m2;
    }
    return (l + r) / 2.0; // 近似极大点
}

• 代码框架（整数域极大值）

// 在整数区间 [l, r] 上极大化 f(i)
long long ternary_search_int(long long l, long long r) {
    auto f = [](long long x) { /* TODO: 定义 f(x) */ return -x*x + 3*x + 1; };
    while (r - l > 3) {
        long long m1 = l + (r - l) / 3;
        long long m2 = r - (r - l) / 3;
        if (f(m1) < f(m2)) l = m1; else r = m2;
    }
    long long bestx = l; auto bestv = f(l);
    for (long long x = l + 1; x <= r; ++x) {
        auto v = f(x);
        if (v > bestv) bestv = v, bestx = x;
    }
    return bestx;
}

• 复杂度与数值注意

  • 每轮舍弃约 1/3 区间，评估次数为 O(log((R−L)/ε))（连续）或 O(log N)（整数）。
  • 函数评估代价大时，可缓存 f(m1)/f(m2) 避免重复计算。
  • 浮点误差：并不要求严格单峰也可工作，但 ε 的选择影响精度与轮次。

• 与黄金分割搜索的关系

  • 黄金分割搜索在连续域同属单峰搜索范式，复用一个内点以减少一次函数评估；收敛速度同阶，常数上黄金分割更优，三分法更直观。

• 应用场景

  • 一维参数调优（代价函数单峰）。
  • 凸/凹函数的极值定位与阈值选择。
  • 组合问题中的离散单峰结构最优点搜索。

关联节点

• 101-数值算法-黄金分割搜索
• 102-数值算法-爬山算法