三分

〇、返回

一、概述

三分算法（Ternary Search）是一种在单峰函数中查找极值点的算法。单峰函数是指在某个区间内先单调递增后单调递减，或者先单调递减后单调递增的函数。三分算法通过将区间分成三部分来逐步缩小搜索范围，从而找到函数的极值点。

二、算法步骤

1. 初始化

设定搜索区间的初始边界，通常为区间的起始位置 left 和结束位置 right。

2. 分割区间

在区间 [left, right] 内找到两个点 mid1 和 mid2，将区间分成三部分。具体计算方法为：

mid1 = left + (right - left) / 3

mid2 = right - (right - left) / 3

3. 比较与缩小范围：

如果 f(mid1) < f(mid2)，则极值点位于区间 [mid1, right] 内，因此更新 left = mid1。

如果 f(mid1) > f(mid2)，则极值点位于区间 [left, mid2] 内，因此更新 right = mid2。

如果 f(mid1) == f(mid2)，则极值点位于区间 [mid1, mid2] 内，可以任意选择更新 left = mid1 或 right = mid2。

4. 终止条件

当区间 [left, right] 足够小（即 right - left 小于某个阈值）时，可以认为找到了极值点，返回 left 或 right 作为极值点的近似位置。

三、适用情况

三分算法适用于以下情况：

单峰函数：函数在某个区间内先单调递增后单调递减，或者先单调递减后单调递增。

查找极值点：需要在单峰函数中找到最大值或最小值点。

优化搜索：在大数据量或高精度要求的情况下，相比暴力搜索，三分搜索能显著提高效率。

四、代码示例（C++）

以下是三分算法的基本实现，假设我们要在一个单峰函数 f(x) 中找到最大值点：

#include<bits/stdc++.h>

using namespace std;

// 示例单峰函数

double f(double x) {

    return -(x*x-4*x+4);        // 这是一个开口向下的二次函数，有唯一最大值点

}

int main() {

    int left=0,right=10

    while (right-left>1e-6) {

        double mid1=left+(right-left)/3,mid2=right-(right-left)/3;

        if (f(mid1)<f(mid2)) {

            left=mid1;

        } else {

            right=mid2;

        }

    }

    double result=(left+right)/2;        // 极值点的近似位置

    cout<<"函数顶点X坐标："<<result<<"\n";

    cout<<"函数顶点Y坐标："<<f(result)<<"\n";

    return 0;

}

五、时间复杂度

三分算法的时间复杂度为 O($log_{\frac{2}{3}} n$)，其中 n 是初始区间的长度。每次迭代都将搜索区间缩小到原来的三分之二，因此能够在对数时间内完成搜索。

六、总结

三分算法是一种在单峰函数中查找极值点的有效方法。其核心思想是通过每次将搜索区间分成三部分来逐步缩小搜索范围，时间复杂度为  O($log_{\frac{2}{3}} n$)，在大数据量或高精度要求的情况下具有显著的优势。理解并掌握三分算法，不仅可以解决基本的极值查找问题，还可以应用于更多复杂的场景，如函数优化、参数调整等。总之，三分算法是处理单峰函数极值问题的一个重要工具。