haar_lib/algo/
golden_search.rs

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