Hands-On Data Structures and Algorithms with Rust

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 ...