Function nekolib::algo::bisect_slice

pub fn bisect_slice<T>(buf: &[T], pred: impl FnMut(&T) -> bool) -> usize

二分探索で境界を探す。

pred(&buf[i]) が false となる最小の i を返す。 ただし i < buf.len() なる全ての i で true の場合は buf.len() を返す。 先頭から i 個の要素が条件を満たすと考えるのがよい。

Requirements

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

Complexity

buf.len() を $n$ として、高々 $\lceil\log_2(n+1)\rceil$ 回の pred の呼び出しを行う。

Examples

use nekolib::algo::bisect_slice;

assert_eq!(bisect_slice(&[2, 4, 7], |&x| x < 4), 1);
assert_eq!(bisect_slice(&[2, 4, 7], |&x| x <= 4), 2);
assert_eq!(bisect_slice(&[2, 4, 7], |&_| false), 0);
assert_eq!(bisect_slice(&[2, 4, 7], |&_| true), 3);