haar_lib/algo/
ternary_search.rs

1//! 三分探索
2
3/// [`ternary_search`]で与えられる関数が上に凸か下に凸かを指定する。
4#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
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 d = (ub - lb) / 3.0;
22        let t1 = lb + d;
23        let t2 = d.mul_add(2.0, lb);
24
25        if (matches!(convex, Convex::Upwards) && f(t1) > f(t2))
26            || (matches!(convex, Convex::Downwards) && f(t1) < f(t2))
27        {
28            ub = t2;
29        } else {
30            lb = t1;
31        }
32
33        loop_count -= 1;
34    }
35
36    lb
37}