pub trait Bisect {
type Input;
type Output;
// Required method
fn bisect(&self, pred: impl FnMut(&Self::Input) -> bool) -> Self::Output;
}Expand description
二分探索。
$\gdef\halfopen#1#2{[#1, #2)}$ 述語 $f$ は、ある $x$ に対して次が成り立つとする。
- $y\in\halfopen{L}{x} \implies f(y)$
- $y\in\halfopen{x}{R} \implies \lnot f(y)$
この $x$ を返す。
Idea
RangeFrom<u32>などに関しては 指数探索。Range<f64>などに関しては ビット表現を整数と見て二分探索。
Notes
下端が条件を満たすかを判定するのが不都合なときは、下端を一つ大きく取って別で処理するとよいかも。 cf. 提出 #34955711
Examples
use nekolib::traits::Bisect;
let pred = |&x: &i32| x * x < 200;
assert_eq!((0..100).bisect(pred), 15);
assert_eq!((0..).bisect(pred), 15);
let a = [0, 1, 4, 5, 5, 5, 9];
let pred = |&x: &i32| x < 5;
assert_eq!(a.bisect(pred), 3);
assert_eq!(a[5..].bisect(pred), 0); // [5, 9]
assert_eq!(a[..0].bisect(pred), 0); // []
let pred = |&x: &f64| 2.0_f64.powf(x) < 3.0;
let lg3 = 3.0_f64.log2();
// 1.584962500721156
assert!(((1.0_f64..2.0).bisect(pred) - lg3).abs() <= 1e-16);
assert_eq!((1.0_f64..2.0).bisect(pred), lg3); // !