三分搜索（Ternary Search）[编辑 | 编辑源代码]

三分搜索是一种用于在单峰函数（Unimodal Function）中寻找极值（最大值或最小值）的算法。与二分搜索（Binary Search）类似，三分搜索通过不断缩小搜索范围来逼近极值点，但它适用于更广泛的函数类型，尤其是那些不具有单调性的函数。

介绍[编辑 | 编辑源代码]

三分搜索的核心思想是将搜索区间分为三个部分，通过比较两个中间点的函数值来缩小搜索范围。该算法适用于连续函数，且函数在极值点的一侧严格递增，另一侧严格递减（即单峰函数）。

单峰函数的定义[编辑 | 编辑源代码]

函数 $f (x)$ 在区间 $[a, b]$ 上是单峰的，如果存在一个点 $c \in [a, b]$ ，使得：

在 $[a, c]$ 上， $f (x)$ 单调递增（或递减）。
在 $[c, b]$ 上， $f (x)$ 单调递减（或递增）。

算法步骤[编辑 | 编辑源代码]

三分搜索的步骤如下： 1. 初始化搜索区间 $[l, r]$ 。 2. 计算两个中间点：

  *  $m_{1} = l + \frac{r - l}{3}$ 
  *  $m_{2} = r - \frac{r - l}{3}$

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}]$ 。

4. 重复上述步骤，直到区间足够小（如 $| r - l | < ϵ$ ）。

可视化[编辑 | 编辑源代码]

代码示例[编辑 | 编辑源代码]

以下是三分搜索的 Python 实现，用于在单峰函数中寻找最大值：

def ternary_search_max(l, r, f, eps=1e-6):
    """
    在区间 [l, r] 中寻找函数 f 的最大值。
    :param l: 区间左端点
    :param r: 区间右端点
    :param f: 单峰函数
    :param eps: 精度阈值
    :return: 极值点的近似值
    """
    while abs(r - l) > eps:
        m1 = l + (r - l) / 3
        m2 = r - (r - l) / 3
        if f(m1) < f(m2):
            l = m1
        else:
            r = m2
    return (l + r) / 2

# 示例函数：f(x) = -x^2 + 4x + 1（在 x=2 处取得最大值 5）
def example_function(x):
    return -x**2 + 4*x + 1

# 测试
max_point = ternary_search_max(0, 4, example_function)
print(f"极值点: {max_point:.4f}, 最大值: {example_function(max_point):.4f}")

输入与输出[编辑 | 编辑源代码]

输入：

区间 $[0, 4]$
函数 $f (x) = - x^{2} + 4 x + 1$

输出：

极值点: 2.0000, 最大值: 5.0000

实际应用场景[编辑 | 编辑源代码]

三分搜索常用于以下场景： 1. 优化问题：在凸函数或凹函数中寻找极值点（如机器学习中的损失函数优化）。 2. 数值分析：求解无法解析求导的函数的极值。 3. 计算机图形学：寻找光线投射中的最近交点或最远点。

案例：抛物线最大值[编辑 | 编辑源代码]

假设我们需要找到抛物线 $f (x) = - 2 x^{2} + 8 x + 3$ 的最大值。使用三分搜索：

初始化区间 $[0, 5]$ 。
经过多次迭代后，算法会收敛到 $x = 2$ ，此时 $f (2) = 11$ 。

时间复杂度[编辑 | 编辑源代码]

三分搜索的时间复杂度为 $O (\log_{1.5} \frac{r - l}{ϵ})$ ，其中 $ϵ$ 是精度阈值。每次迭代将搜索区间缩小为原来的 $\frac{2}{3}$ 。

注意事项[编辑 | 编辑源代码]

1. 确保函数是单峰的，否则算法可能无法找到正确的极值点。 2. 选择适当的精度阈值 $ϵ$ ，避免过早终止或过度计算。

总结[编辑 | 编辑源代码]

三分搜索是一种高效的单峰函数极值搜索算法，适用于无法使用导数或二分搜索的场景。通过合理划分区间和比较函数值，可以快速逼近极值点。