三分搜索算法详解（Python实现与应用场景）

三分搜索 vs 二分搜索

• 二分搜索：适用于有序数组中查找特定值。
• 三分搜索：适用于单峰函数中查找极值（最大值/最小值）。

Python实现三分搜索

下面是一个使用三分搜索查找单峰函数最大值的完整示例。假设我们有一个函数 f(x) = -(x - 5)**2 + 10，它在 x=5 处取得最大值。

def ternary_search_max(func, left, right, precision=1e-9):    """    使用三分搜索查找函数 func 在区间 [left, right] 上的最大值    :param func: 目标函数    :param left: 搜索左边界    :param right: 搜索右边界    :param precision: 精度控制    :return: 极值点 x    """    while right - left > precision:        # 将区间三等分        mid1 = left + (right - left) / 3        mid2 = right - (right - left) / 3                # 计算两个中间点的函数值        f1 = func(mid1)        f2 = func(mid2)                # 如果 mid1 的值小于 mid2，说明最大值在 [mid1, right]        if f1 < f2:            left = mid1        else:            # 否则最大值在 [left, mid2]            right = mid2        return (left + right) / 2# 定义一个单峰函数def example_func(x):    return -(x - 5) ** 2 + 10# 调用三分搜索result_x = ternary_search_max(example_func, 0, 10)print(f"最大值出现在 x ≈ {result_x:.6f}")print(f"最大值为 f(x) ≈ {example_func(result_x):.6f}")

算法步骤解析

1. 设定初始搜索区间 [left, right]。
2. 计算两个三等分点：mid1 = left + (right - left)/3 和 mid2 = right - (right - left)/3。
3. 比较 f(mid1) 和 f(mid2)：
4. 若 f(mid1) < f(mid2)，说明最大值在 [mid1, right]，更新 left = mid1。
5. 否则，最大值在 [left, mid2]，更新 right = mid2。
6. 重复上述过程，直到区间足够小（达到所需精度）。

适用场景与注意事项

✅ 适用场景：

• 单峰函数的极值优化问题（如抛物线、某些代价函数）
• 竞赛编程中的数值优化题
• 机器学习中某些损失函数的参数调优（需满足单峰性）

⚠️ 注意事项：

• 函数必须是单峰的，否则算法可能失效
• 对于离散整数域，需稍作调整（使用整数除法）
• 精度（precision）设置要合理，避免无限循环

总结

通过本篇算法教程，你已经掌握了三分搜索算法的核心思想和Python实现方法。虽然它不如二分搜索常用，但在处理单峰函数极值问题时非常高效。建议动手运行代码，修改函数尝试不同场景，加深理解！

关键词回顾：三分搜索算法、Python三分查找、算法教程、二分搜索进阶。