Linear Search

Linear search or sequential search is a simple method for finding a particular value in a list, that consists of checking every one of its elements, one at a time and in sequence, until the desired one is found. Sequential search on an unsorted list requires Θ(n) time in the worst case.

The performance of linear search improves if the desired value is more likely to be near the beginning of the list than to its end. Therefore, if some values are much more likely to be searched than others, it is desirable to place them at the beginning of the list.

Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an unordered list. When many values have to be searched in the same list, it often pays to pre-process the list in order to use a faster method.

The worst case performance scenario for a linear search is that it needs to loop through the entire collection, either because the item is the last one, or because the item isn't found. In other words, if you have N items in your collection, the worst case scenario to find an item is N iterations. This is known as O(N) using the Big O Notation. The speed of search grows linearly with the number of items within your collection. Linear searches don't require the collection to be sorted.