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
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

//! Implementations of searching algorithms.

use std::cmp::Ordering;

/// An implementation of linear search.
///
/// Looks for the value in the slice by iterating over it. Returns the position
/// of its first equal element, or [`None`] if not found.
///
/// `slice.iter().find(|&x| x == &value)` does almost the same thing.
///
/// # Examples
///
/// ```
/// use search_sort::search;
///
/// let slice = [1, 85, 23, -4, 8];
/// assert_eq!(search::linear(&slice, &23), Some(2));
/// assert_eq!(search::linear(&slice, &-77), None);
/// ```
pub fn linear<T: PartialEq>(slice: &[T], value: &T) -> Option<usize> {
    for (i, v) in slice.iter().enumerate() {
        if value == v {
            return Some(i);
        }
    }

    None
}

/// An implementation of binary search.
///
/// Recursively searches for the value in a sorted slice. It does the following:
/// * computes the center of the slice (size / 2),
/// * compares it with the value,
/// * if it's smaller, invokes itself with the first part of the slice,
/// * if they are equal, returns the center,
/// * if it's greater, invokes itself with the second part of the slice and
///     adds the current center and 1.
/// * if didn't find the value (center == 0 || center >= size - 1), returns
///     [`None`].
///
/// **Note**: the returned value is the position of the first found element,
/// that may not be the position of the first element in the whole slice. Use
/// [`binary_first`] instead.
///
/// # Examples
///
/// ```
/// use search_sort::search;
///
/// let slice = [1, 2, 4, 8, 16, 32];
/// assert_eq!(search::binary(&slice, &8), Some(3));
/// assert_eq!(search::binary(&slice, &3), None);
/// ```
pub fn binary<T: Ord>(slice: &[T], value: &T) -> Option<usize> {
    let mid = slice.len() / 2;
    match value.cmp(&slice[mid]) {
        Ordering::Less if mid > 0 => binary(&slice[0..mid], value),
        Ordering::Equal => Some(mid),
        Ordering::Greater if mid < slice.len() - 1 => {
            match binary(&slice[(mid + 1)..slice.len()], value) {
                Some(x) => Some(x + mid + 1),
                None => None,
            }
        }
        _ => None,
    }
}

/// An implementation of binary search that finds the very first position of
/// the element.
///
/// Invokes [`binary`] search and iterates over the elements backward in
/// the slice before the found element. Returns the position of the last
/// (first in the slice) equal element.
///
/// # Examples
///
/// ```
/// use search_sort::search;
///
/// let fib = [1, 1, 2, 3];
/// // the first found element is on position 1, since it doesn't check the
/// // elements before
/// assert_eq!(search::binary(&fib, &1), Some(1));
/// assert_eq!(search::binary_first(&fib, &1), Some(0));
/// ```
pub fn binary_first<T: Ord>(slice: &[T], value: &T) -> Option<usize> {
    let pos = binary(slice, value);
    match pos {
        Some(pos) => {
            for (i, v) in slice[0..pos].iter().enumerate().rev() {
                if v < value {
                    return Some(i + 1);
                }
            }
            Some(0)
        }
        None => None,
    }
}

#[cfg(test)]
mod tests {
    use super::binary;
    use super::binary_first;
    use super::linear;

    #[test]
    fn linear_test() {
        assert_eq!(linear(&[0, 5, -7, 100, 67, -23], &-7), Some(2));
        assert_eq!(linear(&[11, -25, 12, 85, -8], &6), None)
    }

    #[test]
    fn binary_test() {
        let fib = [1, 1, 2, 3, 5, 8, 13, 21];
        assert_eq!(binary(&fib, &5), Some(4));
        assert_eq!(binary(&fib, &21), Some(7));

        let primes = [1, 2, 3, 5, 7, 11, 13, 17];
        assert_eq!(binary(&primes, &8), None);
        assert_eq!(binary(&primes, &0), None);
        assert_eq!(binary(&primes, &18), None);
    }

    #[test]
    fn binary_first_test() {
        assert_eq!(binary(&[1, 1, 2, 3], &1), Some(1));
        assert_eq!(binary_first(&[1, 1, 2, 3], &1), Some(0));
    }
}