thinkrust_algorithms/
binary_search.rs

1use std::cmp::Ordering;
2
3#[allow(dead_code)]
4pub fn binary_search<T>(list: Vec<T>, item: T) -> Option<usize>
5where
6    T: std::cmp::Ord,
7{
8    if list.is_empty() {
9        return None;
10    };
11    let (mut low, mut high) = (0, list.len() - 1);
12
13    while low < high {
14        let mid = (low + high) / 2;
15
16        match list[mid].cmp(&item) {
17            Ordering::Greater => high = mid,
18            Ordering::Less => low = mid + 1,
19            Ordering::Equal => return Some(mid),
20        }
21    }
22
23    None
24}
25
26#[cfg(test)]
27mod tests {
28    use super::*;
29
30    #[test]
31    fn returns_none_if_items_is_empty() {
32        let items = vec![];
33        let result = binary_search(items, 1);
34
35        assert_eq!(result, None);
36    }
37
38    #[test]
39    fn doesnt_finds_if_collection_is_not_sorted() {
40        let items = vec![1024, 32, 16, 512, 256, 64, 128];
41        let result = binary_search(items, 1024);
42
43        assert_eq!(result, None);
44    }
45
46    #[test]
47    fn finds_index_of_element() {
48        let items = vec![16, 32, 64, 128, 256, 512, 1024];
49        let result = binary_search(items, 256);
50
51        assert_eq!(result, Some(4));
52    }
53}
thinkrust_algorithms/binary_search.rs

thinkrust_algorithms/
binary_search.rs
