1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/// binary search function
pub fn search<T>(list: &[T], item: Option<&T>) -> Option<usize>
where
    T: core::cmp::PartialEq + core::cmp::PartialOrd,
{
    let mut low = 0usize;
    let mut high = list.len(); // or way2: let mut high = list.len() - 1

    // or way2: while low <= high {
    while low < high {
        let mid = (low + high) / 2;
        let guess = list.get(mid);
        if guess == item {
            return Some(mid);
        } else if guess > item {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    None
}

#[test]
fn test_binary_search() {
    let list = vec![1];
    let idx = search(&list, Some(&1));
    println!("idx = {idx:?}");
}