每日算法 — 使用java实现三分搜索：单峰函数极值查找与最优决策

算法背景

三分搜索（Ternary Search）是二分搜索的自然推广，用于在单峰函数（unimodal function）上快速定位极值点。与二分搜索每次排除一半区间不同，三分搜索通过两个中间点将区间划分为三部分，排除不含极值的两段之一，从而实现 $O(\log n)$ 的最优化搜索。

该算法在机器学习超参数调优、经济学边际分析、游戏AI决策评估、物理系统最优控制等场景中均有重要应用。

核心思想

对于定义在区间 $[l, r]$ 上的单峰函数 $f(x)$（先严格递增后严格递减，或反之），取两个三分点：

$$m_1 = l + \frac{r-l}{3}, \quad m_2 = r – \frac{r-l}{3}$$

比较 $f(m_1)$ 与 $f(m_2)$：
– 若 $f(m_1) < f(m_2)$，极值点在 $[m_1, r]$
– 若 $f(m_1) > f(m_2)$，极值点在 $[l, m_2]$
– 若相等，极值点在 $[m_1, m_2]$

每次迭代将搜索区间缩小约 $2/3$。

Java实现：整数域三分搜索

public class TernarySearch {

    /**
     * 在整数区间[l, r]上查找单峰函数的最大值点
     * @param f 单峰函数 (先增后减)
     * @return 使f(x)最大的整数x
     */
    public static int findMaxInt(IntUnaryOperator f, int l, int r) {
        while (r - l > 3) {
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;

            if (f.applyAsInt(m1) < f.applyAsInt(m2)) {
                l = m1; // 最大值在右侧
            } else {
                r = m2; // 最大值在左侧或中间
            }
        }

        // 区间缩小到3个以内时，线性扫描
        int maxVal = f.applyAsInt(l);
        int maxPos = l;
        for (int i = l + 1; i <= r; i++) {
            int val = f.applyAsInt(i);
            if (val > maxVal) {
                maxVal = val;
                maxPos = i;
            }
        }
        return maxPos;
    }

    /**
     * 在整数区间[l, r]上查找单峰函数的最小值点
     */
    public static int findMinInt(IntUnaryOperator f, int l, int r) {
        while (r - l > 3) {
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;

            if (f.applyAsInt(m1) > f.applyAsInt(m2)) {
                l = m1;
            } else {
                r = m2;
            }
        }

        int minVal = f.applyAsInt(l);
        int minPos = l;
        for (int i = l + 1; i <= r; i++) {
            int val = f.applyAsInt(i);
            if (val < minVal) {
                minVal = val;
                minPos = i;
            }
        }
        return minPos;
    }

    public static void main(String[] args) {
        // 示例: f(x) = -x^2 + 10x + 5, 在[0, 20]上的最大值在x=5
        IntUnaryOperator f = x -> -x * x + 10 * x + 5;
        int maxPos = findMaxInt(f, 0, 20);
        System.out.println("Maximum at x = " + maxPos + ", value = " + f.applyAsInt(maxPos));

        // 示例: 数组中找峰值 (先增后减的数组)
        int[] arr = {1, 3, 5, 7, 9, 11, 10, 8, 6, 4, 2};
        IntUnaryOperator arrF = x -> arr[x];
        int peak = findMaxInt(arrF, 0, arr.length - 1);
        System.out.println("Peak index = " + peak + ", value = " + arr[peak]);
    }
}

Java实现：实数域三分搜索

public class TernarySearchDouble {

    private static final double EPS = 1e-9;

    /**
     * 在实数区间[l, r]上查找单峰函数的极大值点
     */
    public static double findMaxDouble(DoubleUnaryOperator f, double l, double r) {
        while (r - l > EPS) {
            double m1 = l + (r - l) / 3.0;
            double m2 = r - (r - l) / 3.0;

            if (f.applyAsDouble(m1) < f.applyAsDouble(m2)) {
                l = m1;
            } else {
                r = m2;
            }
        }
        return (l + r) / 2.0;
    }

    /**
     * 在实数区间[l, r]上查找单峰函数的极小值点
     */
    public static double findMinDouble(DoubleUnaryOperator f, double l, double r) {
        while (r - l > EPS) {
            double m1 = l + (r - l) / 3.0;
            double m2 = r - (r - l) / 3.0;

            if (f.applyAsDouble(m1) > f.applyAsDouble(m2)) {
                l = m1;
            } else {
                r = m2;
            }
        }
        return (l + r) / 2.0;
    }

    public static void main(String[] args) {
        // 示例1: 抛物线顶点 f(x) = -(x-3)^2 + 10
        DoubleUnaryOperator parabola = x -> -(x - 3) * (x - 3) + 10;
        double maxX = findMaxDouble(parabola, -10, 10);
        System.out.printf("Parabola max at x = %.9f, value = %.9f%n", maxX, parabola.applyAsDouble(maxX));

        // 示例2: 寻找最优点使得成本最小
        // cost(x) = x^2 + 10/x, x > 0
        DoubleUnaryOperator cost = x -> x * x + 10.0 / x;
        double optimalX = findMinDouble(cost, 0.1, 10);
        System.out.printf("Optimal x = %.9f, min cost = %.9f%n", optimalX, cost.applyAsDouble(optimalX));
    }
}

游戏AI应用：最优射击角度

public class GameAITernarySearch {

    /**
     * 模拟抛体运动，计算命中目标的射击角度
     * 使用三分搜索寻找使落点最接近目标的角度
     */
    static class ProjectileResult {
        double distance; // 落点距离
        double maxHeight; // 最大高度

        ProjectileResult(double d, double h) { this.distance = d; this.maxHeight = h; }
    }

    static ProjectileResult simulate(double angleDeg, double velocity, double gravity) {
        double angleRad = Math.toRadians(angleDeg);
        double vx = velocity * Math.cos(angleRad);
        double vy = velocity * Math.sin(angleRad);
        double time = 2 * vy / gravity;
        double dist = vx * time;
        double maxH = vy * vy / (2 * gravity);
        return new ProjectileResult(dist, maxH);
    }

    /**
     * 三分搜索最优射击角度
     */
    public static double findOptimalAngle(double targetDist, double velocity, double gravity) {
        DoubleUnaryOperator error = angle -> {
            ProjectileResult r = simulate(angle, velocity, gravity);
            return -Math.abs(r.distance - targetDist); // 负数，越接近0越好
        };

        // 在[1, 89]度范围内搜索
        return TernarySearchDouble.findMaxDouble(error, 1.0, 89.0);
    }

    public static void main(String[] args) {
        double target = 500.0; // 目标距离500米
        double v0 = 100.0;     // 初速100m/s
        double g = 9.8;        // 重力加速度

        double bestAngle = findOptimalAngle(target, v0, g);
        ProjectileResult result = simulate(bestAngle, v0, g);

        System.out.printf("Target distance: %.1f m%n", target);
        System.out.printf("Optimal angle: %.4f degrees%n", bestAngle);
        System.out.printf("Actual distance: %.4f m%n", result.distance);
        System.out.printf("Max height: %.4f m%n", result.maxHeight);
    }
}

高维扩展：三分套三分

对于二元单峰函数 $f(x, y)$，可以外层对 $x$ 三分，内层对 $y$ 三分：

public class NestedTernarySearch {

    /**
     * 二元单峰函数极值搜索
     * 外层三分x，内层三分y
     */
    public static double[] findMax2D(BiFunction<Double, Double, Double> f,
                                      double xl, double xr,
                                      double yl, double yr) {
        double bestX = 0, bestY = 0;

        while (xr - xl > 1e-7) {
            double xm1 = xl + (xr - xl) / 3.0;
            double xm2 = xr - (xr - xl) / 3.0;

            // 对固定的x，三分搜索最优y
            double y1 = findBestY(f, xm1, yl, yr);
            double y2 = findBestY(f, xm2, yl, yr);

            if (f.apply(xm1, y1) < f.apply(xm2, y2)) {
                xl = xm1;
                bestX = xm2;
                bestY = y2;
            } else {
                xr = xm2;
                bestX = xm1;
                bestY = y1;
            }
        }

        return new double[]{bestX, bestY};
    }

    private static double findBestY(BiFunction<Double, Double, Double> f,
                                    double x, double yl, double yr) {
        while (yr - yl > 1e-7) {
            double ym1 = yl + (yr - yl) / 3.0;
            double ym2 = yr - (yr - yl) / 3.0;
            if (f.apply(x, ym1) < f.apply(x, ym2)) {
                yl = ym1;
            } else {
                yr = ym2;
            }
        }
        return (yl + yr) / 2.0;
    }
}

复杂度分析

与黄金分割搜索的对比

应用场景

1. 机器学习: 学习率、正则化系数等超参数的网格搜索优化
2. 经济学: 边际收益等于边际成本时的最优产量决策
3. 游戏开发: NPC行为参数的最优配置
4. 信号处理: 最佳滤波器系数的自适应调整
5. 运筹学: 单变量凸优化问题的快速求解

三分搜索以其实现简洁、理论清晰的特点，成为单峰优化问题的首选算法之一。掌握其原理后，可灵活应用于各类最优决策场景。