binary_search/
lib.rs

1use std::ops::{Add, BitAnd, Shr};
2
3pub trait Betweenable
4where
5    Self: Copy,
6{
7    fn between(x: Self, y: Self) -> Option<Self>;
8}
9
10impl<X> Betweenable for X
11where
12    X: Copy,
13    X: Shr<i8, Output = X>,
14    X: Add<X, Output = X>,
15    X: BitAnd<X, Output = X>,
16    X: From<u8>,
17    X: PartialOrd,
18{
19    fn between(low: Self, high: Self) -> Option<Self> {
20        let one = X::from(1);
21        if high <= low + one {
22            None
23        } else {
24            let mid = (low >> 1) + (high >> 1) + (low & high & one);
25            Some(mid)
26        }
27    }
28}
29
30///
31/// Whether or not the current candidate transition point is lower or higher than the search target.
32///
33pub enum Direction<A, B> {
34    Low(A),
35    High(B),
36}
37
38///
39/// Perform a binary search within the specified bounds.
40///
41/// Given a monotone function, find the largest quantity that is too small and the smallest quantity that is too large.
42///
43/// A user-specified function will be called to determine whether or not an entry is considered lower or higher.
44///
45/// ## Generics
46///
47/// - `X` - the type of the search space. used to specify the bounds of the search and is used for the returned `largest_low` and `smallest_high` values.
48/// - `A` - the type for the low witness.
49/// - `B` - the type for the high witness.
50///
51/// ## Arguments
52/// ### `low`
53/// A tuple specifying the lower bound of the search.
54///
55/// **Expanded as `(lower_bound, witness)` here for brevity.**
56///
57/// - `lower_bound: X` - the lower bound of the search space.\
58/// - `witness: A` - a value passed to the provided function that can be used to verify whether or not a transition is valid.
59///
60/// ### `high`
61/// A tuple specifying the upper bound of the search.
62///
63/// **Expanded as `(upper_bound, witness)` here for brevity.**
64///
65/// - `upper_bound: X` - the upper bound of the search space.\
66/// - `witness: B` - a value passed to the provided function that can be used to verify whether or not a transition is valid.
67///
68/// ### `f`
69/// A `FnMut(X)` function that is called to evaluate each candidate transition point.
70///
71/// #### Arguments
72///
73/// - `X` - the current candidate transition point.
74///
75/// #### Returns
76///
77/// - `Direction` - whether the current candidate transition point is lower or higher than the search target.
78///
79/// ## Return value
80///
81/// Returns a tuple `((largest_low: X, low_witness: A), (smallest_high: X, high_witness: B))`.
82///
83/// - `largest_low: X` - the largest value that the provided function indicated was `Low`.
84/// - `low_witness: A` - the witness value that the provided function last returned inside the `Direction::Low`.
85///
86/// - `smallest_high: X` - the smallest value that the provided function indicated was `High`.
87/// - `high_witness: B` - the witness value that the provided function last returned inside the `Direction::High`.
88///
89/// ## Examples
90///
91/// ```
92/// use binary_search::{binary_search, Direction};
93/// let result = binary_search((1 as usize, ()), (100, ()), |x| {
94/// if x < 23 {
95/// 	Direction::Low(())
96/// } else {
97/// 	Direction::High(())
98/// }
99/// });
100/// assert_eq!(result, ((22, ()), (23, ())))
101/// ```
102///
103pub fn binary_search<X, A, B, F>(low: (X, A), high: (X, B), mut f: F) -> ((X, A), (X, B))
104where
105    X: Betweenable,
106    F: FnMut(X) -> Direction<A, B>,
107{
108    match X::between(low.0, high.0) {
109        None => (low, high),
110        Some(x) => match (f)(x) {
111            Direction::Low(low) => binary_search((x, low), high, f),
112            Direction::High(high) => binary_search(low, (x, high), f),
113        },
114    }
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120
121    #[test]
122    fn split_usize() {
123        assert_eq!(usize::between(1, 0), None);
124        assert_eq!(usize::between(1, 1), None);
125        assert_eq!(usize::between(1, 2), None);
126        assert_eq!(usize::between(1, 3), Some(2));
127        assert_eq!(
128            usize::between(usize::max_value() - 3, usize::max_value() - 1),
129            Some(usize::max_value() - 2),
130        );
131        assert_eq!(
132            usize::between(usize::max_value() - 2, usize::max_value()),
133            Some(usize::max_value() - 1),
134        );
135    }
136
137    #[test]
138    fn binary_search_test() {
139        let result = binary_search((1 as usize, ()), (100, ()), |x| {
140            if x < 23 {
141                Direction::Low(())
142            } else {
143                Direction::High(())
144            }
145        });
146        assert_eq!(result, ((22, ()), (23, ())))
147    }
148
149    #[test]
150    fn binary_search_simple_test() {
151        let values = [0, 4, 5, 6, 7, 9, 456];
152
153        let (largest_low, smallest_high) = binary_search((0, ()), (values.len(), ()), |i| {
154            if values[i] < 6 {
155                Direction::Low(())
156            } else {
157                Direction::High(())
158            }
159        });
160
161        dbg!(largest_low);
162        dbg!(smallest_high);
163    }
164
165    #[test]
166    fn binary_search_witness_test() {
167        let values = [Ok("foo"), Ok("bar"), Ok("baz"), Err(false), Err(true)];
168
169        let (largest_low, smallest_high) =
170            binary_search((0, "bar"), (values.len() - 1, true), |i| {
171                match dbg!(values[dbg!(i)]) {
172                    Ok(x) => Direction::Low(x),
173                    Err(x) => Direction::High(x),
174                }
175            });
176
177        dbg!(largest_low); // "baz"
178        dbg!(smallest_high); // false
179    }
180}
binary_search/lib.rs

binary_search/
lib.rs
