Summary
Search, as a part of the information retrieval (among others) process, is an elementary way of finding something independently of the data structure being used. There are three popular types of algorithm: linear search, jump search, and binary search. Completely different approaches (such as locally-sensitive hashing) have been discussed in an earlier chapter about maps and sets, but they still need a mechanism to compare quickly.
A linear search is the least complex approach: iterate over a collection and compare the items with the element that is to be found. This has also been implemented in Rust's iterator and exhibits O(n) runtime complexity.
Jump searches are superior. By operating on a sorted collection, they can use a step size that is greater than 1 (like a linear search) in order to skip to the required parts faster by checking whether the relevant section has already passed. While faster in absolute terms, the worst-case runtime complexity is still O(n).
The (at the time...
