モチベーション
Rust で二分探索を行う場合 Vec や slice であれば binary_search_by が存在します。
しかし「なんらかの条件を満たす最小の整数」などを求める場合などは
配列などを作ってしまうとメモリを無駄に使うことになります。
実装
trait BinarySearch<T> {
fn binary_search_by<F>(&self, f: F) -> Result<T, T>
where
F: FnMut(&T) -> std::cmp::Ordering;
}
impl<
T: PartialOrd
+ std::ops::Add<Output = T>
+ std::ops::Sub<Output = T>
+ std::ops::Div<Output = T>
+ Copy
+ From<u8>,
> BinarySearch<T> for std::ops::Range<T>
{
fn binary_search_by<F>(&self, mut f: F) -> Result<T, T>
where
F: FnMut(&T) -> std::cmp::Ordering,
{
use std::cmp::Ordering::*;
if self.end <= self.start {
return Err(self.start);
}
let mut base = self.start;
let mut size = self.end - base;
loop {
let half = size / T::from(2);
let mid = base + half;
let cmp = f(&mid);
match cmp {
Less => base = mid,
Equal => return Ok(mid),
_ => {}
}
if T::from(0) == half {
return Err(base + T::from((cmp == Less) as u8));
}
size = size - half;
}
}
}