binary-search

Given a monotone function, find the largest quantity that is too small and the smallest quantity that is too large. The first two arguments to binary_search set the bounds of the search space.

use binary_search::{binary_search, Direction};

fn main() {
  let values =
    [0, 4, 5, 6, 7, 9, 456];

  let (largest_low, smallest_high) =
    binary_search((0, ()), (values.len(), ()), |i|
      if values[i] < 6 {
        Direction::Low(())
      } else {
        Direction::High(())
      }
    );

  dbg!(largest_low);
  dbg!(smallest_high);
}

You can also provide an associated 'witness' as in this example. Witnesses are passed in as well as produced from binary_search. The arguments act as a proof that the function does indeed transition within the range. If you don't know that this is the case, you may need to call your function at the bounds first.

use binary_search::{binary_search, Direction};

fn main() {
  let values =
    [Ok("foo"), Ok("bar"), Ok("baz"), Err(false), Err(true)];

  let (largest_low, smallest_high) =
    binary_search((0, "foo"), (values.len() - 1, true), |i|
      match values[i] {
        Ok(x) => Direction::Low(x),
        Err(x) => Direction::High(x),
      }
    );

  dbg!(largest_low); // "baz"
  dbg!(smallest_high); // false
}