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); // !Required Associated Types§
Required Methods§
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.