rust/binary-search/src/lib.rs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

pub fn find<T: Ord, C: AsRef<[T]>>(array: C, key: T) -> Option<usize> {
    let array = array.as_ref();
    match array.len() {
        0 => None,
        1 => Some(0).filter(|_| array[0] == key),
        n => {
            let mid = n / 2;
            let (a1, a2) = array.split_at(mid);
            if key < array[mid] {
                find(a1, key)
            } else {
                find(a2, key).map(|i| i + mid)
            }
        }
    }
}