算法概述

三分查找（Ternary Search）是一种用于在单峰函数（Unimodal Function）上寻找极值点的搜索算法。单峰函数是指在搜索区间内，函数值先严格递增再严格递减（凸函数/求最大值）或先严格递减再严格递增（凹函数/求最小值）的函数。

与二分查找每次将搜索范围缩小一半不同，三分查找每次将搜索范围缩小到原来的 2/3。每次在区间内取两个三等分点，比较它们的函数值后丢弃 1/3 的区间。

核心思想

假设我们要在区间 [L, R] 上求凹函数（先减后增）的最小值：

1. 取两个分点 m1 = L + (R - L) / 3 和 m2 = R - (R - L) / 3。
2. 比较 f(m1) 和 f(m2)：
   • 若 f(m1) < f(m2)：最小值不可能在 [m2, R] 区间，丢弃右侧，令 R = m2。
   • 若 f(m1) > f(m2)：最小值不可能在 [L, m1] 区间，丢弃左侧，令 L = m1。
   • 若 f(m1) == f(m2)：最小值在 [m1, m2] 内，令 L = m1, R = m2。
3. 重复直到区间足够小，取 (L + R) / 2 作为近似解。

关键前提：目标函数在搜索区间内必须是单峰的。如果是多峰函数，三分查找不能保证找到全局极值。

算法步骤 / 伪代码

求凹函数最小值

function ternarySearch(L, R, f, eps):
    while R - L > eps:                    // eps 为精度要求
        m1 = L + (R - L) / 3
        m2 = R - (R - L) / 3
        if f(m1) < f(m2):
            R = m2                        // 丢弃右 1/3
        else if f(m1) > f(m2):
            L = m1                        // 丢弃左 1/3
        else:
            L = m1;  R = m2               // 极值在中间
    return (L + R) / 2

求凸函数最大值

只需将比较方向反转即可：

function ternarySearchMax(L, R, f, eps):
    while R - L > eps:
        m1 = L + (R - L) / 3
        m2 = R - (R - L) / 3
        if f(m1) < f(m2):
            L = m1                        // 丢弃左 1/3
        else:
            R = m2                        // 丢弃右 1/3
    return (L + R) / 2

C++ 代码实现

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

// ============ 示例函数 ============

// 凹函数（先减后增）：f(x) = (x-3)^2 + 2，在 x=3 处取最小值 2
double f1(double x) {
    return (x - 3) * (x - 3) + 2;
}

// 凸函数（先增后减）：f(x) = -(x-2)^2 + 5，在 x=2 处取最大值 5
double f2(double x) {
    return -(x - 2) * (x - 2) + 5;
}

// 更复杂的凹函数：f(x) = x^4 - 4x^3 + 5x^2 - 2x + 1
double f3(double x) {
    return x*x*x*x - 4*x*x*x + 5*x*x - 2*x + 1;
}

// ============ 三分查找：求凹函数最小值 ============
double ternarySearchMin(double L, double R, double (*f)(double), 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;          // 最小值在左侧 2/3
        } else if (f(m1) > f(m2)) {
            L = m1;          // 最小值在右侧 2/3
        } else {
            L = m1; R = m2;  // 极值在中间
        }
    }
    return (L + R) / 2.0;
}

// ============ 三分查找：求凸函数最大值 ============
double ternarySearchMax(double L, double R, double (*f)(double), 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 = m1;          // 最大值在右侧 2/3
        } else {
            R = m2;          // 最大值在左侧 2/3
        }
    }
    return (L + R) / 2.0;
}

// ============ 三分查找：离散整数版本（求数组中的极小值位置）============
// 适用于严格先递减再递增的数组（相邻元素不相等）
int ternarySearchDiscrete(const vector<int>& arr, int L, int R) {
    while (R - L > 2) {   // 至少需要 3 个元素才能三分
        int m1 = L + (R - L) / 3;
        int m2 = R - (R - L) / 3;

        if (arr[m1] < arr[m2]) {
            R = m2;
        } else {
            L = m1;
        }
    }
    // 区间缩小后在 [L, R] 中暴力查找最小值
    int minIdx = L;
    for (int i = L + 1; i <= R; ++i) {
        if (arr[i] < arr[minIdx]) minIdx = i;
    }
    return minIdx;
}

// ============ 主函数 ============
int main() {
    cout << fixed << setprecision(10);
    cout << "========== 三分查找演示 ==========" << endl << endl;

    // ---- 示例 1：求 f1(x) = (x-3)^2 + 2 在 [0, 6] 的最小值 ----
    double x_min1 = ternarySearchMin(0.0, 6.0, f1);
    cout << "f1(x) = (x-3)^2 + 2 在 [0, 6] 的最小值:" << endl;
    cout << "  x = " << x_min1 << ", f(x) = " << f1(x_min1) << endl;
    cout << "  期望: x = 3, f(x) = 2" << endl << endl;

    // ---- 示例 2：求 f2(x) = -(x-2)^2 + 5 在 [0, 5] 的最大值 ----
    double x_max = ternarySearchMax(0.0, 5.0, f2);
    cout << "f2(x) = -(x-2)^2 + 5 在 [0, 5] 的最大值:" << endl;
    cout << "  x = " << x_max << ", f(x) = " << f2(x_max) << endl;
    cout << "  期望: x = 2, f(x) = 5" << endl << endl;

    // ---- 示例 3：求 f3(x) 在 [-1, 3] 的最小值 ----
    double x_min3 = ternarySearchMin(-1.0, 3.0, f3);
    cout << "f3(x) = x^4 - 4x^3 + 5x^2 - 2x + 1 在 [-1, 3] 的最小值:" << endl;
    cout << "  x = " << x_min3 << ", f(x) = " << f3(x_min3) << endl << endl;

    // ---- 示例 4：离散三分查找 ----
    vector<int> arr = {10, 8, 5, 3, 1, 2, 4, 7, 12}; // 先减后增
    cout << "数组: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    int idx = ternarySearchDiscrete(arr, 0, arr.size() - 1);
    cout << "最小值的下标: " << idx << ", 值: " << arr[idx] << endl;
    cout << "期望: 下标 4, 值 1" << endl;

    return 0;
}

复杂度分析

指标	值
时间	O(log n)（以 3/2 为底，实际等同于 O(log n)）
空间	O(1)
每次迭代	丢弃 1/3 的搜索区间
每次迭代计算	2 次函数求值
前提	函数在搜索区间内必须是单峰的

• 时间复杂度推导：每次迭代后区间变为原来的 2/3。设初始区间长度为 n，经过 k 次迭代后区间长度为 n × (2/3)^k。当区间长度小于精度 ε 时停止，即 n × (2/3)^k < ε，解得 k > log_{3/2}(n/ε)，因此时间复杂度为 O(log n)。

• 与二分查找的比较：

  • 二分查找每次计算 1 次函数值，丢弃 1/2 区间。
  • 三分查找每次计算 2 次函数值，丢弃 1/3 区间。
  • 从理论效率上看，三分查找的常数略大。但在需要求极值的单峰函数场景中，二分查找无法直接使用。

应用场景

1. 求凸/凹函数的极值：在无法通过求导解析求解的优化问题中，使用三分查找数值逼近极值点。例如机器学习中的超参数调优（学习率、正则化系数等）。

2. 一维优化问题：如"最小化加工时间"、"求最短距离"等可以转化为单峰函数最小化的问题。

3. 计算几何：求点到曲线的最近距离、求最大内切圆半径等问题。

4. 三分答案：类似于"二分答案"，当判定函数 f(x) 在某区间内满足单峰性时，可用三分查找求最优解。

5. 竞赛编程：Codeforces、AtCoder 等竞赛中常出现单峰函数求极值的题目，三分查找是标准解法。

经典例题

求凸函数的最小值

问题描述：给定一个在 [L, R] 上先严格递减再严格递增的凹陷函数 f(x)，求其最小值点 x* 及最小值 f(x*)。

示例：f(x) = (x - 3)² + 2 在 x = 3 处取得最小值 2。

三分查找解法思路：

1. 在 [L, R] 内取两个三等分点 m1 和 m2。
2. 比较 f(m1) 和 f(m2)：
   • 对于求最小值（凹函数），若 f(m1) < f(m2)，最小值不可能在 m2 右侧，丢弃 [m2, R]。
   • 若 f(m1) > f(m2)，最小值不可能在 m1 左侧，丢弃 [L, m1]。
3. 不断缩小范围直至精度满足要求。

变体：找单峰数组的峰值

如果有一个"先严格递增再严格递减"的数组（如山脉数组），可以用三分查找或二分查找找到峰值位置（LeetCode 852 / 162）。虽然这是求最大值而非最小值，但核心思想一致——利用单峰性质每次丢弃一部分搜索空间。

（完整 C++ 代码已包含在上方的代码实现中）