编辑“︁三分搜索（Ternary Search）”︁（章节）

= 三分搜索（Ternary Search） =

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

== 介绍 ==

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

=== 单峰函数的定义 ===
函数 <math>f(x)</math> 在区间 <math>[a, b]</math> 上是单峰的，如果存在一个点 <math>c \in [a, b]</math>，使得：
* 在 <math>[a, c]</math> 上，<math>f(x)</math> 单调递增（或递减）。
* 在 <math>[c, b]</math> 上，<math>f(x)</math> 单调递减（或递增）。

== 算法步骤 ==

三分搜索的步骤如下：
1. 初始化搜索区间 <math>[l, r]</math>。
2. 计算两个中间点：
   * <math>m_1 = l + \frac{r - l}{3}</math>
   * <math>m_2 = r - \frac{r - l}{3}</math>
3. 比较 <math>f(m_1)</math> 和 <math>f(m_2)</math>：
   * 如果 <math>f(m_1) < f(m_2)</math>，则极值点位于 <math>[m_1, r]</math>。
   * 如果 <math>f(m_1) > f(m_2)</math>，则极值点位于 <math>[l, m_2]</math>。
4. 重复上述步骤，直到区间足够小（如 <math>|r - l| < \epsilon</math>）。

=== 可视化 ===
<mermaid>
graph TD
    A[初始化区间 [l, r]] --> B[计算 m1 = l + (r - l)/3, m2 = r - (r - l)/3]
    B --> C{比较 f(m1) 和 f(m2)}
    C -->|f(m1) < f(m2)| D[更新区间为 [m1, r]]
    C -->|f(m1) > f(m2)| E[更新区间为 [l, m2]]
    D --> F{检查终止条件}
    E --> F
    F -->|未满足| B
    F -->|满足| G[返回极值点]
</mermaid>

== 代码示例 ==

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

<syntaxhighlight lang="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}")
</syntaxhighlight>

=== 输入与输出 ===
输入：
* 区间 <math>[0, 4]</math>
* 函数 <math>f(x) = -x^2 + 4x + 1</math>

输出：
<pre>
极值点: 2.0000, 最大值: 5.0000
</pre>

== 实际应用场景 ==

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

=== 案例：抛物线最大值 ===
假设我们需要找到抛物线 <math>f(x) = -2x^2 + 8x + 3</math> 的最大值。使用三分搜索：
* 初始化区间 <math>[0, 5]</math>。
* 经过多次迭代后，算法会收敛到 <math>x = 2</math>，此时 <math>f(2) = 11</math>。

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

== 注意事项 ==
1. 确保函数是单峰的，否则算法可能无法找到正确的极值点。
2. 选择适当的精度阈值 <math>\epsilon</math>，避免过早终止或过度计算。

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:搜索算法]]