The Complete Rust Programming Reference Guide

Jump search

Going linearly over a collection one-by-one is only efficient if you are already close to a potential match, but it is very hard to determine—what does close to a match mean? In unordered collections, this is indeed impossible to know this since any item can follow. Consequently, what about sorting the collection first? As discussed in Chapter 19, Ordering Things, sorting at quasi-linear runtime complexity can be significantly faster than going over each item of a long collection past a certain size.

A jump search makes use of knowing about the range it jumps over, not unlike a skip list:

After sorting, a search can be significantly ...