1use core::cmp::Ordering;
2
3/// An implementation of binary search on indices only
4/// that does not require slices to be constructed. Mirrors
5/// the semantics of binary_search_by in the standard library.
6pub fn binary_search<F>(mut start: usize, mut end: usize, mut f: F) -> Result<usize, usize>
7where
8 F: FnMut(usize) -> Ordering,
9{
10 loop {
11 let mid: usize = start + (end - start) / 2;
12 if mid == end {
13 return Err(start);
14 }
15 match f(mid) {
16 Ordering::Less => start = mid + 1,
17 Ordering::Greater => end = mid,
18 Ordering::Equal => return Ok(mid),
19 }
20 }
21}
22
23#[test]
24fn test_binary_search() {
25 assert_eq!(binary_search(0, 5000, |x| x.cmp(&1337)), Ok(1337));
26 assert_eq!(binary_search(0, 5000, |x| x.cmp(&9000)), Err(5000));
27 assert_eq!(binary_search(30, 50, |x| x.cmp(&42)), Ok(42));
28 assert_eq!(binary_search(300, 500, |x| x.cmp(&42)), Err(300));
29 assert_eq!(
30 binary_search(0, 500, |x| if x < 42 {
31 Ordering::Less
32 } else {
33 Ordering::Greater
34 }),
35 Err(42)
36 );
37}
38