三分搜索

介绍

三分搜索（Ternary Search）是一种用于在单峰函数（即先递增后递减，或先递减后递增的函数）中寻找极值（最大值或最小值）的算法。它的核心思想是通过不断缩小搜索范围来逼近极值点。与二分搜索类似，三分搜索也是一种分治算法，但它通过将搜索区间分为三部分来实现。

三分搜索的时间复杂度为 O(log3 n)，比二分搜索的 O(log2 n) 稍高，但在某些特定场景下（如单峰函数）非常高效。

算法原理

三分搜索的基本步骤如下：

1. 确定搜索区间的左边界 left 和右边界 right。
2. 将区间分为三个部分，计算两个中间点 mid1 和 mid2：
   • mid1 = left + (right - left) / 3
   • mid2 = right - (right - left) / 3
3. 比较 f(mid1) 和 f(mid2) 的值：
   • 如果 f(mid1) < f(mid2)，则极值点位于 [mid1, right] 区间。
   • 如果 f(mid1) > f(mid2)，则极值点位于 [left, mid2] 区间。
4. 重复上述步骤，直到搜索区间足够小。

备注

三分搜索适用于单峰函数。如果函数有多个极值点，三分搜索可能无法找到全局极值。

代码示例

以下是一个使用三分搜索寻找单峰函数最大值的 Python 示例：

python

def ternary_search(left, right, f, precision=1e-6):
    while abs(right - left) > precision:
        mid1 = left + (right - left) / 3
        mid2 = right - (right - left) / 3

        if f(mid1) < f(mid2):
            left = mid1
        else:
            right = mid2

    return (left + right) / 2

# 示例函数：f(x) = -x^2 + 4x + 5
def f(x):
    return -x**2 + 4*x + 5

# 搜索区间为 [0, 5]
max_point = ternary_search(0, 5, f)
print(f"函数的最大值出现在 x = {max_point:.6f}")

输入：

• 搜索区间 [0, 5]
• 函数 f(x) = -x^2 + 4x + 5

输出：

函数的最大值出现在 x = 2.000000

提示

在实际应用中，可以通过调整 precision 参数来控制搜索的精度。

实际案例

案例 1：寻找抛物线顶点

假设我们需要找到抛物线 f(x) = -x^2 + 4x + 5 的顶点。这是一个典型的单峰函数，其顶点即为最大值点。使用三分搜索可以高效地找到顶点的位置。

案例 2：优化问题

在某些优化问题中，目标函数可能是单峰的。例如，在机器学习中，某些损失函数在特定区间内是单峰的。使用三分搜索可以快速找到损失函数的最小值。

总结

三分搜索是一种高效的算法，适用于在单峰函数中寻找极值。它的核心思想是通过将搜索区间分为三部分来逐步缩小范围，从而逼近极值点。虽然它的时间复杂度略高于二分搜索，但在特定场景下非常有用。

附加资源与练习

1. 练习 1：尝试实现一个三分搜索算法，寻找函数 f(x) = x^3 - 6x^2 + 11x - 6 在区间 [0, 4] 内的最小值。
2. 练习 2：比较三分搜索和二分搜索在相同函数上的性能差异。
3. 资源：阅读更多关于分治算法的资料，了解其他类似的搜索算法。

警告

三分搜索仅适用于单峰函数。如果函数有多个极值点，建议使用其他优化算法，如梯度下降或牛顿法。