Linear search

A search, also called a sequential search, is simply a loop through a collection with some kind of comparison function to locate a matching element or value. Most linear searches return a value representing the index of the matching object in the collection, or some impossible index value such as -1 when an object is not found. Alternative versions of this search could return the object itself or null if the object is not found.

This is the simplest form of search pattern and it carries an O(n) complexity cost. This complexity is consistent whether the collection is in random order or if it has already been sorted. In very small collections linear searches are perfectly acceptable and many developers make use of them daily. However, when working with very large collections it is often beneficial to find alternatives to this sequential search approach. This is particularly true when working with lists of very complex objects, such as spatial geometries, where search or...