Linear search, explained

Linear search is the simplest way to find something. You look at the first item, then the next, and keep going until you find what you want or run out of items.

It does not need the list to be sorted, which makes it the safe choice when you know nothing about the data.

How it works

• Start at the first position.
• Compare the item with the target.
• If it matches, stop: you found it.
• If not, move to the next position. If you reach the end, the target is not in the list.

A small example

Search for 23 in this sorted list:

2 5 8 12 16 23 38 56 72 91

Linear search checks 2, 5, 8, 12, 16 and 23, so it takes:

6 checks (found at position 6)

What to know about its cost

• Best case O(1) when the target is first.
• Average and worst case O(n).
• Uses O(1) extra space and needs no sorted list.

Where it works well

• Works on unsorted data.
• Very simple, and fast enough for short lists.

Where it struggles

• Slow for long lists, because it may check every item.
• Ignores any order the data has.

Try it yourself

Open the Searching experiment, enter the list from this post, set the target to 23, choose Linear Search and step through it. Then compare it with the other algorithms and look at how many positions each one checks.

Open the Searching experiment