算法刷题系列（二十三）：三分搜索——在单峰函数中定位极值

算法刷题系列（二十三）：三分搜索——在单峰函数中定位极值

二分查找用单调真假条件定位边界；当目标是单峰函数的极值时，可比较区间内部的两个点，舍弃不可能包含极值的一侧。三分搜索看似通用，实际上必须先有单峰或离散凸性等前提。任意函数上每轮比较两个点，并不能保证找到全局极值。

一、两个内部点提供什么信息

在区间 [left, right] 内取 m1、m2，使 m1 < m2。若函数先降后升，且 f(m1) < f(m2)，谷底不可能在 m2 的右侧：在右侧函数已经更高，区间可缩到 [left, m2]。反过来，若 f(m1) > f(m2)，则可缩到 [m1, right]。

对于离散整数区间，另一个常用写法比较相邻点 f(mid) 与 f(mid + 1)。若 f(mid) <= f(mid + 1)，最小值可留在左侧至 mid；否则留在 mid + 1 及右侧。它本质上是对“相邻差值符号从负变正”的边界进行二分。

二、整数最小值：定位离散谷底

假设整数定义域连续，函数先不增后不减（允许平台）。区间最终缩成一个点；该点是最小值所在位置之一。平台上返回哪一个端点取决于比较规则，不影响最小值。

public class Main {
    static int argMin(int left, int right) {
        while (left < right) {
            int mid = (int) (left + ((long) right - left) / 2);
            if (cost(mid) <= cost(mid + 1)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    static long cost(int x) {
        return (long) (x - 7) * (x - 7) + 3;
    }

    public static void main(String[] args) {
        int at = argMin(-20, 30);
        assert at == 7;
        assert cost(at) == 3;
        assert argMin(7, 7) == 7;
    }
}

三、实数最小值：控制误差

连续定义域通常无法用有限次比较精确表示极值点。固定执行若干轮后，返回区间中点作为近似值。每轮区间长度约缩为原来的 2/3，因此迭代 k 次后误差上界与初始长度乘以 (2/3)^k 同阶。

def ternary_min(left: float, right: float, iterations: int = 100) -> float:
    if left > right:
        raise ValueError("left must not exceed right")

    def cost(x: float) -> float:
        return (x - 2.5) ** 2 + 1.0

    for _ in range(iterations):
        third = (right - left) / 3.0
        m1 = left + third
        m2 = right - third
        if cost(m1) <= cost(m2):
            right = m2
        else:
            left = m1
    return (left + right) / 2.0

answer = ternary_min(-10.0, 12.0)
assert abs(answer - 2.5) < 1e-7

四、Java 实数版本

import java.util.function.DoubleUnaryOperator;

public class Main {
    static double ternaryMin(
            double left, double right, int iterations,
            DoubleUnaryOperator function) {
        if (left > right || iterations < 0) {
            throw new IllegalArgumentException("invalid interval or iteration count");
        }
        for (int i = 0; i < iterations; i++) {
            double third = (right - left) / 3.0;
            double m1 = left + third;
            double m2 = right - third;
            if (function.applyAsDouble(m1) <= function.applyAsDouble(m2)) {
                right = m2;
            } else {
                left = m1;
            }
        }
        return left + (right - left) / 2.0;
    }

    public static void main(String[] args) {
        double answer = ternaryMin(-10.0, 12.0, 100,
                x -> (x - 2.5) * (x - 2.5) + 1.0);
        assert Math.abs(answer - 2.5) < 1e-7;
        assert ternaryMin(3.0, 3.0, 10, x -> x * x) == 3.0;
    }
}

实数版本的时间复杂度为 O(k) 次函数计算，额外空间为 O(1)。整数相邻比较版本每轮减半，时间复杂度为 O(log(R-L+1))，其中 L、R 是整数边界。

五、前提与易错点

1. 先验证形状：需要全区间单峰；多个不相连的谷底可能使局部比较丢失全局最优。
2. 整数边界：mid + 1 必须仍在范围内，因此循环条件用 left < right，并保证中点小于 right。
3. 平台处理：<= 的分支会把相等平台的候选保留在左边，不会漏掉最小值。
4. 浮点精度：迭代轮数按目标误差选择；不要期待返回值与数学极值的浮点表示完全相等。
5. 最大值：若函数先升后降，比较方向应相应反转，或者对 -f(x) 求最小值。

小结与衔接

三分搜索通过比较区间内部点缩小单峰函数的候选区域。它适用于满足结构假设的优化问题，不是二分查找的万能替代。若候选答案由有限个动态变化的元素组成，下一篇会转向堆：不缩小连续区间，而是在插入与删除中维护当前最值。