Function nekolib::algo::bisect_::bisect

pub fn bisect(_: Range<usize>, pred: impl FnMut(usize) -> bool) -> usize

二分探索で境界を探す。

pred(i) が false となる最小の i を返す。 ただし start..end 内の全ての i で true の場合は end を返す。

Requirements

pred(i) が false となる i が存在するとき、i < j なる全ての j で pred(j) が false となる。

Complexity

区間の長さを $n$ として、高々 $\lceil\log_2(n+1)\rceil$ 回の pred の呼び出しを行う。

Suggestions

範囲の型を PrimInt なり Ord なりにしたい気もする。区間長と中間値の取得をよしなにできると助かる。

Examples

use nekolib::algo::bisect;

let floor_sqrt = |i| if i <= 1 { i } else {
    bisect(0..i, |j| match (j + 1).overflowing_pow(2) {
        (x, false) if x <= i => true,
        _ => false
    })
};
assert_eq!(floor_sqrt(8), 2);
assert_eq!(floor_sqrt(9), 3);
assert_eq!(floor_sqrt(10), 3);
assert_eq!(floor_sqrt(1 << 60), 1 << 30);