binary_search/
lib.rs

1use std::ops::{Shr, Add, BitAnd};
2
3pub trait Betweenable where Self: Copy {
4  fn between(x: Self, y: Self) -> Option<Self>;
5}
6
7impl<X> Betweenable for X
8    where
9      X: Copy,
10      X: Shr<i8, Output=X>,
11      X: Add<X, Output=X>,
12      X: BitAnd<X, Output=X>,
13      X: From<u8>,
14      X: PartialOrd {
15  fn between(low: Self, high: Self) -> Option<Self> {
16    let one = X::from(1);
17    if high <= low + one {
18      None
19    } else {
20      let mid = (low >> 1) + (high >> 1) + (low & high & one);
21      Some(mid)
22    }
23  }
24}
25
26pub enum Direction<A, B> {
27  Low(A),
28  High(B),
29}
30
31pub fn binary_search<X, A, B, F>(
32    low: (X, A),
33    high: (X, B),
34    mut f: F,
35  ) -> ((X, A), (X, B))
36  where
37    X: Betweenable,
38    F: FnMut(X) -> Direction<A, B> {
39  match X::between(low.0, high.0) {
40    None => {
41      (low, high)
42    },
43    Some(x) => {
44      match (f)(x) {
45        Direction::Low(low) => {
46          binary_search((x, low), high, f)
47        },
48        Direction::High(high) => {
49          binary_search(low, (x, high), f)
50        },
51      }
52    }
53  }
54}
55
56#[cfg(test)]
57mod tests {
58  use super::*;
59
60  #[test]
61  fn split_usize() {
62    assert_eq!(usize::between(1, 0), None);
63    assert_eq!(usize::between(1, 1), None);
64    assert_eq!(usize::between(1, 2), None);
65    assert_eq!(usize::between(1, 3), Some(2));
66    assert_eq!(
67      usize::between(usize::max_value()-3, usize::max_value()-1),
68      Some(usize::max_value()-2),
69    );
70    assert_eq!(
71      usize::between(usize::max_value()-2, usize::max_value()),
72      Some(usize::max_value()-1),
73    );
74  }
75
76  #[test]
77  fn binary_search_test() {
78    let result =
79      binary_search((1 as usize, ()), (100, ()), |x| {
80        if x < 23 {
81          Direction::Low(())
82        } else {
83          Direction::High(())
84        }
85      });
86    assert_eq!(result, ((22, ()), (23, ())))
87  }
88}
binary_search/lib.rs

binary_search/
lib.rs
