モチベーション

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;
    }
  }
}

使用例