binary-search

Binary search is often used to find the position at which a value is located within a sorted array. However, the general idea is more broadly applicable than that.

Given a function that returns a Direction indicating whether the value is too low or too high, this library will find the transition point.

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
}