## binary-search

General binary search implementation

### 3 releases

 0.1.2 May 8, 2021 Oct 30, 2018 Oct 30, 2018

#855 in Data structures

Used in 4 crates (3 directly)

5KB
81 lines

# 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
}
``````