alg_ds/alg/
search.rs

1/// Looking for the maximum element.
2///
3pub fn max<T>(list: &[T]) -> Option<usize>
4where
5    T: PartialOrd,
6{
7    if list.is_empty() {
8        return None;
9    }
10    let mut max_idx = 0;
11    let mut max_val = &list[max_idx];
12    for idx in 0..list.len() {
13        if list[idx] > *max_val {
14            max_idx = idx;
15            max_val = &list[idx];
16        }
17    }
18    Some(max_idx)
19}
20
21/// Looking for the minimum element.
22///
23pub fn min<T>(list: &[T]) -> Option<usize>
24where
25    T: PartialOrd,
26{
27    if list.is_empty() {
28        return None;
29    }
30    let mut min_idx = 0;
31    let mut min_val = &list[min_idx];
32    for idx in 0..list.len() {
33        if list[idx] < *min_val {
34            min_idx = idx;
35            min_val = &list[idx];
36        }
37    }
38    Some(min_idx)
39}
40
41/// Binary search in slice.
42///
43pub fn binary<T>(list: &[T], item: T) -> Option<usize>
44where
45    T: PartialOrd,
46{
47    if list.is_empty() {
48        return None;
49    }
50
51    let mut lhs = 0;
52    let mut rhs = list.len() - 1;
53
54    while lhs <= rhs {
55        let mid = (lhs + rhs) / 2;
56        if list[mid] > item {
57            rhs = mid - 1;
58        } else if list[mid] < item {
59            lhs = mid + 1;
60        } else {
61            return Some(mid);
62        }
63    }
64    None
65}
66
67#[cfg(test)]
68mod tests {
69
70    use super::*;
71
72    #[test]
73    fn max_ok() {
74        let list = [10, 12, 45, 23, 29, 100, 1000, 0, 12];
75        assert_eq!(max(&list).unwrap(), 6);
76
77        let list: &[i32] = &[];
78        assert_eq!(max(list), None);
79    }
80
81    #[test]
82    fn min_ok() {
83        let list = [10, 12, 45, 23, 29, 100, 1000, 0, 12];
84        assert_eq!(min(&list).unwrap(), 7);
85
86        let list: &[i32] = &[];
87        assert_eq!(min(list), None);
88    }
89
90    mod binary {
91
92        #[test]
93        fn binary_integer_ok() {
94            let list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
95            assert_eq!(super::binary(&list, 7).unwrap(), 6);
96
97            let list = [5];
98            assert_eq!(super::binary(&list, 5).unwrap(), 0);
99
100            let list = [5, 5, 5];
101            assert_eq!(super::binary(&list, 5).unwrap(), 1);
102
103            let list = [];
104            assert_eq!(super::binary(&list, 0), None);
105        }
106
107        #[test]
108        fn binary_float_ok() {
109            let list = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0];
110            assert_eq!(super::binary(&list, 7.0).unwrap(), 6);
111
112            let list = [1.000, 1.0005, 1.001, 1.0015, 1.0016, 2.0];
113            assert_eq!(super::binary(&list, 1.0015).unwrap(), 3);
114        }
115
116        #[test]
117        fn binary_str_ok() {
118            let list = ["a", "a", "b", "e", "f"];
119            assert_eq!(super::binary(&list, "e").unwrap(), 3);
120
121            let list = ["aaa", "aab", "abb", "abc", "bcd"];
122            assert_eq!(super::binary(&list, "aab").unwrap(), 1);
123        }
124
125        #[test]
126        fn binary_string_ok() {
127            let list = [
128                "a".to_string(),
129                "a".to_string(),
130                "b".to_string(),
131                "e".to_string(),
132                "f".to_string(),
133            ];
134            assert_eq!(super::binary(&list, "e".to_string()).unwrap(), 3);
135
136            let list = [
137                "aaa".to_string(),
138                "aab".to_string(),
139                "abb".to_string(),
140                "abc".to_string(),
141                "bcd".to_string(),
142            ];
143            assert_eq!(super::binary(&list, "aab".to_string()).unwrap(), 1);
144        }
145    }
146}
alg_ds/alg/search.rs

alg_ds/alg/
search.rs
