第 27 课 - 三分搜索

课程：数据结构与算法
当前课：第 27 课 - 三分搜索
所属模块：搜索算法
难度：中级
标签：ternary, unimodal, peak
上一课：指数搜索
下一课：二叉树基础

1. 学习目标

通过本课学习，你将能够：

理解单峰函数（unimodal function）的概念及其特征
掌握三分搜索算法的原理与实现方法
分析三分搜索的时间复杂度和适用场景
应用三分搜索解决实际的极值查找问题
区分三分搜索与二分搜索的异同点

2. 核心概念

什么是单峰函数？

单峰函数是指在一个区间内，函数先递增再递减（或先递减再递增），存在且仅存在一个极值点的函数。想象一座山峰：从山脚开始向上爬，到达山顶后开始下山——这个“山顶”就是极值点。

    *        <-- 极值点（峰）
   * *
  *   *
 *     *
*       *

三分搜索原理

三分搜索是在单峰函数上寻找极值点的高效算法。它将当前搜索区间 [left, right] 分成三等分，取两个中间点：

m1 = left + (right - left) / 3
m2 = right - (right - left) / 3

通过比较 f(m1) 和 f(m2) 的值：

若 f(m1) < f(m2)，则极值点在 [m1, right] 区间
若 f(m1) > f(m2)，则极值点在 [left, m2] 区间
若 f(m1) == f(m2)，则极值点在 [m1, m2] 区间

每次迭代将搜索区间缩小至原来的 2/3，效率比线性搜索高得多！

与二分搜索的区别

特性	二分搜索	三分搜索
目标	查找特定值	查找极值点
函数要求	单调函数	单峰函数
区间划分	2等分	3等分
比较次数	1次	2次

3. 代码示例

def ternary_search(func, left, right, epsilon=1e-9):
    """
    三分搜索算法 - 查找单峰函数的极值点（最大值）
    
    参数：
        func: 单峰函数 f(x)
        left: 搜索区间左边界
        right: 搜索区间右边界
        epsilon: 精度要求（停止条件）
    
    返回：
        极值点的x坐标
    """
    while right - left > epsilon:
        # 计算两个三分点
        m1 = left + (right - left) / 3
        m2 = right - (right - left) / 3
        
        # 比较两个点的函数值
        f1 = func(m1)
        f2 = func(m2)
        
        if f1 < f2:
            # 极值点在 [m1, right] 区间
            left = m1
        else:
            # 极值点在 [left, m2] 区间
            right = m2
    
    # 返回区间的中点作为极值点
    return (left + right) / 2

def example_function(x):
    """示例单峰函数：f(x) = -(x-3)^2 + 10（最大值在x=3处）"""
    return -(x - 3)**2 + 10

# 测试三分搜索
if __name__ == "__main__":
    print("=== 三分搜索示例 ===")
    
    # 定义搜索区间和精度
    left, right = 0, 6  # 包含极值点x=3
    epsilon = 1e-6
    
    # 执行搜索
    max_x = ternary_search(example_function, left, right, epsilon)
    max_y = example_function(max_x)
    
    print(f"函数: f(x) = -(x-3)^2 + 10")
    print(f"搜索区间: [{left}, {right}]")
    print(f"找到的极值点: x = {max_x:.6f}")
    print(f"极值: f(x) = {max_y:.6f}")
    print(f"实际最大值点: x = 3.000000, f(x) = 10.000000")

代码说明：

ternary_search 函数接受目标函数、区间和精度参数
使用 while 循环迭代缩小搜索范围，直到区间小于 epsilon
每次迭代计算两个三分点并比较函数值，决定保留哪部分区间
示例函数 -(x-3)^2 + 10 在 x=3 处有最大值 10

4. 实践练习

练习 1：基础实现（简单）

要求：实现一个三分搜索函数，找到函数 f(x) = x^2 - 4x + 5 在区间 [0, 5] 上的最小值。

提示：

先将函数转换为单峰形式（或直接处理凹函数）
确定是寻找最大值还是最小值
调整比较逻辑

预期输出：

最小值点: x = 2.000000
最小值: f(x) = 1.000000

练习 2：处理非严格单峰函数（中等）

要求：修改三分搜索算法，使其能够处理函数值在某个区间内相等的情况（平台情况）。例如函数 f(x) = 10 - |x - 3| 在 [2, 4] 区间内值恒为 10。

要求：

当 f(m1) == f(m2) 时，同时缩小左右边界
保证算法不会无限循环

练习 3：实际应用（挑战）

要求：给定一个长度为 n 的数组 arr，其中元素先严格递增再严格递减（单峰数组），找到峰值元素。

示例输入：

arr = [1, 3, 5, 7, 9, 11, 10, 8, 6, 4, 2]

预期输出：

峰值位置: 5
峰值元素: 11

5. 常见错误

错误 1：误用二分搜索

# ❌ 错误：用二分搜索找单峰函数的极值
def binary_search_peak(func, left, right):
    # 这通常无法正确找到极值点！
    mid = (left + right) / 2
    # ... 后续逻辑无法处理单峰情况

正确做法：确认函数特性，选择合适的算法。

错误 2：忽略边界条件

# ❌ 错误：没有考虑区间完全包含在单侧的情况
def bad_ternary_search(func, left, right):
    # 假设函数在 [left, right] 上单调递增
    # 没有验证函数是否真的单峰
    m1 = left + (right - left) / 3
    m2 = right - (right - left) / 3
    # ... 可能得到错误结果

正确做法：

验证函数在区间内是否单峰
处理边界情况（单调区间）

错误 3：精度设置不当

# ❌ 错误：精度设置太小或太大
epsilon = 1e-20  # 可能导致无限循环（浮点精度限制）
epsilon = 1      # 精度太低，结果不准确

正确做法：根据实际需求设置合理精度，通常 1e-6 或 1e-9 是合适的。

错误 4：函数非单峰

# ❌ 错误：将非单峰函数传入三分搜索
def multi_peak_function(x):
    return np.sin(x) * x  # 有多个极值点

# 三分搜索会找到局部极值，不一定是全局极值

正确做法：确认函数特性，或使用其他全局优化算法。

6. 小结

关键要点回顾

单峰函数：只有一个极值点的函数，先增后减或先减后增
三分搜索原理：通过将区间三等分并比较两个三分点的函数值，逐步缩小搜索范围
算法特点：
- 时间复杂度：O(log₃/₂ n) ≈ O(1.71 log n)
- 空间复杂度：O(1)（迭代实现）
- 每次迭代需要计算两次函数值
适用场景：
- 单峰函数的极值查找
- 优化问题中的单峰目标函数
- 某些竞赛题目中的特定问题

与前序知识的联系

指数搜索（上一课）：用于无界或大型有序数据集
三分搜索（本课）：用于单峰函数的极值查找
二叉树基础（下一课）：三分搜索的“三分”思想与二叉树的分支结构有相似之处

下一步学习

学习完三分搜索后，建议：

了解其他极值查找算法（如斐波那契搜索）
探索多维极值问题（梯度下降等）
为下一课“二叉树基础”做准备，理解树形数据结构

思考题：三分搜索能否用于寻找单峰函数的最小值？如何修改算法实现？

练习编辑器

rust