haar_lib/algo/
ternary_search.rs

1//! 三分探索
2
3/// [`ternary_search`]で与えられる関数が上に凸か下に凸かを指定する。
4#[derive(Clone, Copy, Debug, PartialEq)]
5pub enum Convex {
6    /// 上に凸
7    Upwards,
8    /// 下に凸
9    Downwards,
10}
11
12/// 三分探索
13pub fn ternary_search<F: Fn(f64) -> f64>(
14    mut lb: f64,
15    mut ub: f64,
16    convex: Convex,
17    mut loop_count: usize,
18    f: F,
19) -> f64 {
20    while loop_count > 0 {
21        let t1 = lb + (ub - lb) / 3.0;
22        let t2 = lb + (ub - lb) / 3.0 * 2.0;
23
24        if (matches!(convex, Convex::Upwards) && f(t1) > f(t2))
25            || (matches!(convex, Convex::Downwards) && f(t1) < f(t2))
26        {
27            ub = t2;
28        } else {
29            lb = t1;
30        }
31
32        loop_count -= 1;
33    }
34
35    lb
36}