Linear search

Linear search is what you do when you look for a name on an unsorted list: start at the top and read down until you find it. It is the simplest search there is, it works on any list, and for short lists it is often all you need.

Bars of a list checked one by one from the start, the checked bars faded, a dashed line at the target height and the matching bar highlighted
Bars of a list checked one by one from the start, the checked bars faded, a dashed line at the target height and the matching bar highlighted

The idea

Compare the target with the first value of the list. If they are equal, stop: the target is at place 1. Otherwise compare it with the second value, then the third, and so on. If the last value does not match either, the target is not in the list. Nothing about the list needs to be known in advance: it does not have to be sorted, and the values can be anything that can be compared for equality.

An example

Search 5, 1, 4, 2, 8 for 4. Is 5 equal to 4? No. Is 1? No. Is 4? Yes: found at place 3 after 3 comparisons. Now search the same list for 7. Each of the five values is checked and none matches, so after 5 comparisons the answer is that 7 is not there.

How many comparisons

A value at place k takes k comparisons to find. If the target is equally likely to be at any place, that is (n + 1)/2 comparisons on average: 20.5 for 40 values. A value that is missing always takes n, because only after the last comparison is it certain that no value matched. So the cost grows in proportion to the length of the list, which is written O(n).

Faster searches need order

Linear search cannot skip anything, because in an unsorted list any value could be anywhere. Once a list is sorted, a comparison tells you more than equal or not: it tells you which side the target is on. Binary search uses that to halve the list at every step and needs about log₂ n comparisons, at most 6 for 40 values. Sorting costs time too, though, so for a list that is searched only once, linear search is often the better choice.

Small improvements

A sentinel version puts the target at the end of the list before searching, so the loop only has to test for a match and not also for the end of the list. Moving a value one place forward, or to the front, every time it is found makes frequently searched values cheaper over time. Neither changes the worst case of n comparisons.

Explore it

Open the app, choose a value in Search for, and press Step. The dashed line shows the target's height, each value is highlighted as it is checked and faded once it is ruled out, and a match turns green. Search for a value that is not in the list to see a full pass, or turn off Stop at the first match and use few unique values to find several matches.

Frequently asked questions

What is the time complexity of linear search?

O(n) in the worst and average case, and O(1) in the best case, when the target is the first value. It needs no extra memory.

What is the difference between linear search and binary search?

Linear search checks every value in order and works on any list. Binary search only works on a sorted list, but it halves the part that can hold the target at every step, so it needs about log₂ n comparisons instead of up to n.

Does linear search need a sorted list?

No. That is its main advantage. On a sorted list it can stop as soon as it passes the place where the target would be, but it is still slower than binary search.

Where is linear search used?

Everywhere lists are short or unsorted: finding an item in a small array, scanning a file or a stream that can only be read in order, or checking every element for a condition. Many library functions, such as indexOf in JavaScript and list.index in Python, are linear searches.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try linear search