An implementation of Fibonacci-section method to find the maximum of a unimodal sequence.

fibonacci_section.rs

/// Searches the maximum value of `query` in section between `lower` (exclusive) and `upper` (exclusive).
fn fibonacci_section(lower: usize, upper: usize, mut query: impl FnMut(usize) -> u32) -> u32 {
    let n = upper - lower - 1;
    if n == 1 {
        return query(1);
    }
    let mut fib = vec![1, 2];
    for i in 2.. {
        let next = fib[i - 2] + fib[i - 1];
        if next > n {
            break;
        }
        fib.push(next);
    }
    let fib = fib;

    let mut start = lower;
    for win in fib.windows(2).rev() {
        let [step_left, step_right] = win else {
            unreachable!()
        };
        let mid_left = start + step_left;
        let mid_right = start + step_right;
        if mid_right > n {
            continue;
        }
        let mid_left_value = query(mid_left);
        let mid_right_value = query(mid_right);
        if mid_left_value < mid_right_value {
            start = mid_left;
        }
    }
    (start + 1..upper).take(2).map(query).max().unwrap()
}