Rust语言中的三分搜索算法详解（从零开始掌握高效查找技术）

什么是三分搜索？

三分搜索（Ternary Search）是一种分治算法，主要用于在单峰函数（unimodal function）上寻找最大值或最小值。所谓单峰函数，是指函数先单调递增后单调递减（或反之），只有一个“峰”或“谷”。

与二分查找每次将区间一分为二不同，三分搜索将当前搜索区间分成三等份，通过比较两个分割点的函数值，排除掉不可能包含极值的三分之一区间，从而逐步逼近目标。

适用场景

• 在凸函数/凹函数上找极值
• 在有序但非线性变化的数据中定位峰值
• 优化问题中的参数调优（如机器学习超参数搜索）

Rust 实现三分搜索

下面我们用 Rust 编写一个通用的三分搜索函数，用于在整数区间 [left, right] 上寻找单峰函数的最大值。

// 定义目标函数：例如 f(x) = -(x - 5)^2 + 10，这是一个开口向下的抛物线fn target_function(x: i32) -> i32 {    return -(x - 5) * (x - 5) + 10;}// 三分搜索：在 [left, right] 区间内寻找最大值fn ternary_search(left: i32, right: i32) -> i32 {    let mut l = left;    let mut r = right;    while r - l > 3 {        let m1 = l + (r - l) / 3;        let m2 = r - (r - l) / 3;        let f1 = target_function(m1);        let f2 = target_function(m2);        if f1 < f2 {            // 最大值在 [m1, r] 区间            l = m1;        } else {            // 最大值在 [l, m2] 区间            r = m2;        }    }    // 在剩余的小范围内暴力搜索最大值    let mut best = target_function(l);    for x in (l + 1)..=r {        best = best.max(target_function(x));    }    best}fn main() {    let result = ternary_search(0, 10);    println!("函数最大值为: {}", result); // 输出应为 10}

代码解析

1. target_function 是我们待优化的单峰函数。这里使用了一个简单的二次函数作为例子。

2. 在 ternary_search 函数中：

• 我们计算两个三分点 m1 和 m2。
• 比较 f(m1) 和 f(m2) 的大小。
• 如果 f(m1) < f(m2)，说明最大值在右半部分，因此舍弃左三分之一；否则舍弃右三分之一。
• 当区间足够小时（长度 ≤ 3），直接遍历剩余点以确保精度。

为什么选择 Rust？

Rust 以其内存安全、零成本抽象和高性能著称，非常适合实现底层算法。通过本例，你不仅能掌握三分查找实现的核心思想，还能熟悉 Rust 的基本语法和函数式风格。

总结

三分搜索是解决单峰优化问题的强大工具。通过本篇Rust算法教程，你已经学会了如何在 Rust 中实现它。记住：三分搜索仅适用于单峰函数，若用于普通有序数组查找元素，应优先考虑二分查找。

动手试试修改 target_function，看看能否找到其他函数的极值吧！