C++三分搜索算法详解（从零开始掌握高效搜索技巧）

适用场景

• 在连续或离散的单峰/单谷函数中找极值
• 优化问题，如最小化最大距离、最大化收益等
• 不能使用导数但函数具有单调性变化的问题

C++三分搜索算法实现步骤

假设我们要在一个定义在区间 [left, right] 上的单峰函数 f(x) 中找到最大值点。

1. 计算两个三分点：
   m1 = left + (right - left) / 3
m2 = right - (right - left) / 3
2. 比较 f(m1) 和 f(m2) 的大小
3. 如果 f(m1) < f(m2)，说明最大值在 [m1, right] 区间，更新 left = m1
4. 否则，最大值在 [left, m2] 区间，更新 right = m2
5. 重复上述过程，直到区间足够小（例如小于一个精度 epsilon）

完整C++代码示例

下面是一个在单峰函数 f(x) = -(x - 5)*(x - 5) + 10 上查找最大值的C++三分查找实现：

#include <iostream>#include <cmath>using namespace std;// 定义单峰函数：f(x) = -(x-5)^2 + 10double f(double x) {    return -(x - 5) * (x - 5) + 10;}// 三分搜索函数：在 [left, right] 区间找最大值double ternarySearch(double left, double right) {    const double eps = 1e-9; // 精度控制        while (right - left > eps) {        double m1 = left + (right - left) / 3.0;        double m2 = right - (right - left) / 3.0;                if (f(m1) < f(m2)) {            left = m1; // 最大值在右三分之二区间        } else {            right = m2; // 最大值在左三分之二区间        }    }        return (left + right) / 2.0; // 返回极值点位置}int main() {    double left = 0.0, right = 10.0;    double result = ternarySearch(left, right);        cout << "最大值出现在 x = " << result << endl;    cout << "最大值为 f(x) = " << f(result) << endl;        return 0;}

时间复杂度分析

每次迭代都将搜索区间缩小为原来的 2/3，因此时间复杂度为 O(log₃ n)，其中 n 是初始区间的长度（或元素个数）。这与二分查找的 O(log₂ n) 处于同一数量级，都是高效的高效搜索算法。

注意事项

• 确保函数确实是单峰或单谷的，否则结果不可靠
• 对于整数域上的问题，循环条件可改为 while (right - left >= 3)，最后暴力检查剩余点
• 浮点数比较需注意精度问题，使用 epsilon 控制终止条件

总结

通过本教程，你已经掌握了C++三分搜索算法的基本原理、实现方法和应用场景。无论是解决算法竞赛题还是实际工程中的优化问题，这项技术都能为你提供强大支持。记住，关键在于识别问题是否具有单峰/单谷性质——这是应用该C++算法教程所授知识的前提。

动手尝试修改上面的函数，看看能否在其他单峰函数上成功找到极值吧！