Linear Search

What is linear search?

Linear search looks for a value, called the key, by checking every item in order. It starts at the first item and asks “is this the key?” If yes, it returns the position. If not, it moves one step right. If it reaches the end without a match, the key isn’t there, and it returns −1.

It is the search you do when you look for a name on an unsorted paper list: top to bottom, one line at a time. It is also called sequential search.

Its big strength is that it works on any list. The values don’t have to be sorted. Every faster search on this site needs sorted input.

How it works, step by step

Press play above. The key is shown next to the counters. The blue bar is being compared with the key, and lo marks where the search is. Every bar behind lo fades out: it has been ruled out. A green bar is the match.

1. Set lo = 0 and hi to the last index.
2. Compare a[i] with the key.
3. If they are equal, return i. Done.
4. If not, everything up to i is ruled out, so move lo to i + 1.
5. Repeat until you find the key or pass the end. Then return −1.

Try both presets. With “present”, the search stops as soon as it hits the key. With “absent”, it has to check every single value before it can say no.

The array in this demo happens to be sorted, so the searches on this site can share the same inputs. Linear search doesn’t use that at all. It would behave the same on a shuffled list.

Time and space complexity

Best case, O(1): the key is the first value. One comparison.

Worst case, O(n): the key is the last value, or not there at all. Every value gets checked.

Average case, O(n): if the key is equally likely to be anywhere, you check about half the list, n/2 comparisons. Big-O drops the ½, so it is still O(n).

Space is O(1). One index, no copies.

O(n) sounds slow next to binary search’s O(log n). For a million values, that is up to a million checks versus about 20. But binary search needs sorted input, and sorting costs O(n log n). If you only search once, sorting first costs more than just looking.

Common mistakes

• Returning −1 inside the loop, right after the first mismatch. The “not found” answer can only come after the loop ends.
• Off-by-one on the end. In Python, range(lo, hi + 1) includes hi. In a C-style loop, use i <= hi or i < n.
• Using linear search over and over on the same big list. If you search many times, sort once and use binary search, or put the values in a hash set for O(1) lookups.

When to use it

Linear search is the right choice more often than people think:

• The list is unsorted and you only search it once or a few times.
• The list is small. For a few dozen values, a straight scan is often faster than anything clever, because it reads memory in order.
• You are searching a stream or a linked list, where you can’t jump to the middle anyway.
• You need the first match by some rule, like the first word longer than 10 letters.

Most languages have it built in: list.index in Python, Array.prototype.indexOf and find in JavaScript, and slices.Index in Go all do a linear scan.

Questions

Does linear search need a sorted list?

No. That is its main advantage. It works on any list, in any order.

Is linear search faster than binary search?

On small lists it can be. On large sorted lists, binary search is far faster: O(log n) against O(n).

What does linear search return if the key is missing?

By convention, −1: a position that can’t exist, so the caller knows nothing was found.