Linear search

The classic linear search is provided via position() (or rposition()) on the Iterator<T> trait, and it even utilizes other iterator functions that are implemented on the trait itself:

fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
    Self: Sized,
    P: FnMut(Self::Item) -> bool,
{
    // The addition might panic on overflow
    self.try_fold(0, move |i, x| {
        if predicate(x) { LoopState::Break(i) }
        else { LoopState::Continue(i + 1) }
    }).break_value()
}

try_fold() is a short-circuit variation on the fold() (or reduce(), following the map/reduce pattern) function that returns whenever LoopState::Break is returned. The call to break_value() transforms the result from the value returned in the LoopState::Break enumeration into Option and None if it ran through the entire collection.

This is the brute-force approach to searching and can be useful if the collection is unsorted and short. For anything longer, sorting and...