C语言三分搜索算法详解（手把手教你实现高效非线性查找）

适用场景

• 在连续或离散的单峰函数中找最大值/最小值
• 优化问题中的极值求解（如抛物线顶点）
• 无法使用二分查找的非单调但有唯一极值的问题

注意：三分搜索不适用于普通有序数组的查找（那是二分查找的领域），它的核心价值在于处理非线性搜索问题。

算法原理

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

1. 计算两个中间点：m1 = left + (right - left) / 3 和 m2 = right - (right - left) / 3
2. 比较 f(m1) 和 f(m2)：
• 如果 f(m1) < f(m2)，说明最大值在 [m1, right] 区间，更新 left = m1
• 如果 f(m1) > f(m2)，说明最大值在 [left, m2] 区间，更新 right = m2
• 如果相等，可任选一侧（通常保留 [m1, m2]）
3. 重复上述过程，直到区间足够小（精度满足要求）

C语言实现示例

下面是一个在离散整数数组中查找单峰最大值的 C语言三分搜索 实现：

#include <stdio.h>// 示例单峰函数：先增后减int f(int x) {    return -(x - 5) * (x - 5) + 25; // 顶点在 x=5，最大值为25}int ternarySearch(int left, int right) {    while (right - left > 3) { // 当区间足够小时停止        int m1 = left + (right - left) / 3;        int m2 = right - (right - left) / 3;                if (f(m1) < f(m2)) {            left = m1; // 最大值在右2/3区间        } else {            right = m2; // 最大值在左2/3区间        }    }        // 在最后几个点中暴力查找最大值    int maxVal = f(left);    for (int i = left + 1; i <= right; i++) {        if (f(i) > maxVal) {            maxVal = f(i);        }    }    return maxVal;}int main() {    int result = ternarySearch(0, 10);    printf("最大值为: %d\n", result);    return 0;}

这段代码演示了如何使用三分搜索在函数 f(x) = -(x-5)² + 25 中找到最大值。该函数在 x=5 处取得最大值 25，程序会正确输出结果。

时间复杂度分析

每次迭代将搜索区间缩小为原来的 2/3，因此时间复杂度为 O(log₃ n)，与二分查找的 O(log₂ n) 同属对数级别，实际效率略低，但在适用场景下是最佳选择。

总结

通过本教程，你已经掌握了C语言三分搜索的基本原理和实现方法。记住，三分搜索不是万能的，它专为非线性搜索中的单峰极值问题而生。在面对合适的场景时，它能提供优雅高效的解决方案。

希望这篇C语言算法教程能帮助你打开算法设计的新思路！动手尝试修改示例代码，用不同的函数测试你的三分搜索实现吧。