三分查找算法完整详解（C# 原生实现，无第三方库）-尧图网络科技

基本概念

二分查找（Binary Search）

适用条件：

仅适用于单调函数或单调数组（严格递增/递减）
典型应用：在有序数组中查找指定数值（如升序数组中的元素定位）

目标：
通过不断折半缩小搜索范围，将时间复杂度从 O(n) 优化至 O(log n)。例如在数组[1, 3, 5, 7, 9]中查找 5，通过比较中间值 5 可直接命中目标。

三分查找（Ternary Search）

适用条件：

严格单峰函数：函数在区间内先严格递增至唯一极大值点，后严格递减（如抛物线-x²）
严格单谷函数：函数在区间内先严格递减至唯一极小值点，后严格递增（如抛物线x²）

核心目标：
寻找区间内的极值点（最大值或最小值的位置）。通过将区间分为三部分，比较中间两点的函数值，逐步缩小极值所在范围。

分类：

浮点三分
- 适用于连续实数区间的数学函数极值求解（如求f(x) = -x² + 4x的顶点）
- 终止条件：区间长度小于预设精度（如1e-6）
整数三分
- 适用于离散整数区间（如数组索引、离散优化问题）
- 典型场景：在单峰数组[2, 3, 5, 4, 1]中查找峰值 5 的索引
- 终止条件：区间长度 ≤ 3，需手动比较剩余点

⚠️ 关键前提：
区间内必须严格单峰或单谷，即仅存在一个极值点。多峰函数（如sin(x)在[0, 2π]区间）需结合其他方法（如模拟退火）处理。

历史背景

三分查找作为分治搜索算法的重要代表，其发展与二分搜索密切相关。二分搜索最早由约翰·莫奇利（John Mauchly）于1946年在Moore School Lectures中提出，并于1948年由德博拉·布朗（Derrick Henry Lehmer）正式发表。这一算法对计算机科学领域产生了深远影响。

在数值优化的发展过程中，研究人员发现传统单调搜索方法在处理凸函数极值问题时存在明显局限。20世纪60年代末至70年代初，数学家们基于二分区间压缩的思想，创新性地提出了三分区间迭代策略。该策略通过将搜索区间分为三部分进行比较，有效解决了非单调凸函数的极值点定位问题。

早期三分查找主要应用于数值计算领域，尤其在函数最优化问题上表现出色。随着算法竞赛的兴起，20世纪90年代起，三分查找因其高效性被广泛应用于各类编程竞赛，并成为ACM/ICPC等国际赛事中解决特定问题的标准工具之一。

如今，三分查找的应用范围已相当广泛，主要包括：

函数最优化：用于寻找凸函数或单峰函数的极值点
最优决策枚举：在离散优化问题中定位最佳决策点
凸包计算：辅助计算凸包的相关参数
斜率优化DP：作为动态规划斜率优化的关键求解方法

从数学本质上看，三分查找并非完全创新的算法，而是二分思想在非单调凸函数场景下的自然扩展。它继承了分治算法的核心理念，并通过更精细的区间划分策略，拓展了二分搜索的应用范围。

核心原理详解

搜索区间设置

首先需要确定一个初始搜索区间 [a, b]，这个区间必须满足：

对于单峰函数（先增后减，求最大值）：要保证函数在区间内存在极大值点
对于单谷函数（先减后增，求最小值）：要保证函数在区间内存在极小值点

示例：对于函数，若要求最大值，可以选取初始区间 [0, 5]，因为函数在 x=2 处达到最大值。

取三分点

在区间 [a, b] 内取两个三分点：

这样将区间分为三等份，保证 m1 和 m2 对称分布且 m1 < m2。

函数值比较

计算并比较和的值：

情况1：求最大值（单峰函数）

若：极大值不可能在，舍弃左段，新区间更新为
若：极大值不可能在，舍弃右段，新区间更新为
若：极大值在内，可任选一侧舍弃

情况2：求最小值（单谷函数）

若：极小值不可能在，舍弃左段，新区间更新为
若：极小值不可能在，舍弃右段，新区间更新为
若：极小值在内，可任选一侧舍弃

迭代过程

重复上述步骤，每次迭代都将搜索区间缩小为原来的 2/3。随着迭代进行，区间会不断收敛到极值点所在位置。

终止条件

当满足以下任一条件时停止迭代：

区间长度小于预设精度 ε（对于浮点数）
- 例如
区间长度小于等于阈值 T（对于整数问题）
- 例如 T = 1

算法特性

每次迭代需要计算 2 个新函数值
收敛速度为线性收敛，比二分法略慢
适用于导数难以求得或不存在的情况
可以处理离散函数的最优化问题

应用场景：

工程设计中的参数优化
机器学习中的超参数调优
金融模型中的最佳投资比例确定
物理实验中的最佳条件寻找

实现注意：

建议使用相对误差而非绝对误差来判断收敛
可以设置最大迭代次数防止无限循环
对于高维问题需要配合其他方法使用

执行流程

【浮点三分执行流程】

输入：区间左边界，右边界，精度，目标函数

循环条件：当区间长度时，继续迭代。
计算三分点：
- 计算中点
- 计算中点
计算函数值：
- 计算和
缩小区间（基于单峰性质）：
- 若（求极小值），则令
- 否则，令
输出结果：循环结束后，区间中点即为极值的近似位置。

示例（求函数极小值）：
设，在[0, 5]区间内寻找极小值点。
每次迭代将区间缩小 1/3，最终收敛到x ≈ 2（极小值点）。

【整数三分执行流程】

输入：整数区间，离散函数

循环条件：当时继续迭代（避免死循环）。
计算中点（防溢出写法）：
比较函数值：
- 计算和
收缩边界：
- 若（求极小值），则令
- 否则，令
最终检查：在内枚举剩余点（通常 2~3 个），取最优解。

注意事项：

死循环风险：若循环条件写为，可能因或导致无限循环。
边界调整：确保每次迭代区间缩小，避免原地踏步。

示例（离散函数优化）：
设为某离散函数，在[1, 10]内寻找最小值点。
每次迭代后区间缩小至[L, R]，最终在剩余 2~3 个点中选取最优值。

❗重要提醒：

整数三分需严格处理边界条件，确保算法终止。

算法性能分析

时间复杂度分析

该算法采用三分法（Ternary Search）进行区间缩减。在每轮迭代中，搜索区间会缩小为原来的。设初始区间长度为，经过次迭代后，区间长度满足：

其中为预设的精度阈值。求解该不等式可得迭代次数 (k) 的表达式：

因此，算法的时间复杂度为。根据对数换底公式，该复杂度可进一步简化为，与二分查找（Binary Search）的时间复杂度相同。但需注意，三分法的常数因子略高于二分法，因为每轮迭代需计算两个中间点（而二分法仅需一个）。

空间复杂度分析

算法的空间复杂度为 (O(1))，仅需使用少量临时变量（如左右端点、中间点等）维护当前搜索区间，不依赖于输入规模 (n)。因此，这是一种原地迭代算法，无需额外的数组或复杂数据结构支持。

精度特性分析

浮点三分：
受浮点数精度限制，该算法无法得到完全精确的解，而是通过预设的误差阈值控制结果精度。例如，在求解单峰函数的极值点时，算法会在区间长度小于时终止，此时区间内的任意一点均可作为近似最优解。

示例：优化问题时，若设，算法会输出一个接近理论最小值点 (x = -1) 的近似值。

整数三分：
当问题定义在离散整数域（如数组下标）时，三分法可通过精确的区间缩减找到唯一最优点。由于每次迭代的区间边界均为整数，结果不存在浮点误差。

应用场景：在离散的单峰序列（如先递增后递减的数组）中，整数三分可高效定位确切的峰值位置。

对比与扩展

与二分法的对比：
三分法适用于单峰函数或序列的极值搜索，而二分法通常用于单调性问题（如有序数组查找）。三分法的每轮迭代需两次函数计算（或值比较），因此常数时间开销更高。

优化技巧：
在实现时，可通过记忆化（缓存函数计算结果）减少重复计算，尤其当函数评估开销较大（如涉及复杂模拟或神经网络推断）时效果显著。

完整原生代码

浮点三分查找（连续函数・求单峰最大值）

using System; namespace TernarySearchDemo { class Program { // 待求极值 单峰测试函数：f(x) = - (x - 3)^2 + 9 // 理论极大值点 x=3，最大值=9 static double Func(double x) { return -(x - 3) * (x - 3) + 9; } /// <summary> /// 浮点三分查找【单峰函数最大值】 /// </summary> /// <param name="left">区间左边界</param> /// <param name="right">区间右边界</param> /// <param name="eps">精度阈值</param> /// <returns>极值点x坐标</returns> static double TernarySearchDouble(double left, double right, double eps = 1e-8) { while (right - left > eps) { double m1 = left + (right - left) / 3; double m2 = right - (right - left) / 3; double f1 = Func(m1); double f2 = Func(m2); if (f1 < f2) { // 峰值在右侧 [m1, right] left = m1; } else { // 峰值在左侧 [left, m2] right = m2; } } return (left + right) / 2; } static void Main(string[] args) { double peakX = TernarySearchDouble(0, 6); double maxVal = Func(peakX); Console.WriteLine($"极值点 X = {peakX:F8}"); Console.WriteLine($"函数最大值 = {maxVal:F8}"); } } }

整数三分查找（离散区间・单峰序列最大值）

注意整数三分标准防死循环写法

using System; namespace TernarySearchDemo { class Program { // 离散单峰函数示例 static int DiscreteFunc(int x) { return - (x - 8) * (x - 8) + 64; // 最大值在 x=8 } /// <summary> /// 整数三分 寻找离散单峰函数最大值位置 /// </summary> static int TernarySearchInt(int left, int right) { while (left < right) { int m1 = left + (right - left) / 3; int m2 = right - (right - left) / 3; int f1 = DiscreteFunc(m1); int f2 = DiscreteFunc(m2); if (f1 < f2) { left = m1 + 1; } else { right = m2 - 1; } } return left; } static void Main(string[] args) { int bestX = TernarySearchInt(0, 16); Console.WriteLine($"离散最优位置：{bestX}"); Console.WriteLine($"最大值：{DiscreteFunc(bestX)}"); } } }

通用封装（委托版本，任意函数传入）

适合工程使用，不需要重复写查找逻辑

using System; namespace TernarySearchDemo { class Program { static double TestFunc(double x) { return -x * x + 4 * x; } // 使用Func委托实现通用三分 static double TernarySearchGeneric(double l, double r, Func<double, double> f, double eps = 1e-8) { while (r - l > eps) { double m1 = l + (r - l) / 3; double m2 = r - (r - l) / 3; if (f(m1) < f(m2)) l = m1; else r = m2; } return (l + r) / 2; } static void Main() { double res = TernarySearchGeneric(-2, 4, TestFunc); Console.WriteLine($"极值点：{res:F6}"); } } }