Linear search visualization

Linear search (also called sequential search) finds a value in a list by checking the elements one by one, from the first to the last, until it finds the target or runs out of elements. It works on any list, sorted or not.

How it works

1. Start at index 0.
2. Compare the element at the current index with the target.
3. If they are equal, return the current index.
4. Otherwise move to the next index and go back to item 2.
5. If you pass the last element without a match, return -1.

A worked example of linear search

Search for 4 in [7, 3, 9, 4, 1, 8, 5]. Each round compares one element with the target:

1. Index 0 holds 7. That is not 4.
2. Index 1 holds 3. That is not 4.
3. Index 2 holds 9. That is not 4.
4. Index 3 holds 4. It equals 4, so return 3.

The result is 3 after 4 comparisons, and indexes 4 to 6 are never looked at. Now search the same array for 6, which is not in it. Every element is compared, so there are 7 comparisons, and the result is -1.

Linear search pseudocode

Indexes start at 0, as in the code of this lesson. A is the array and n is its length.

LINEAR-SEARCH(A, n, target)
1  for i = 0 to n - 1
2      if A[i] == target
3          return i
4  return -1

The loop runs at most n rounds and makes one comparison in each, which is where the O(n) worst case comes from.

Time and space complexity

Each round of the loop is one comparison, so the work grows in a straight line with the length of the array.

Complexity

Best case time	O(1)
Average case time	O(n)
Worst case time	O(n)
Extra space	O(1)

• Best, O(1): the target is the first element, so one comparison is enough.
• Average, O(n): if the target is equally likely to be anywhere, about half the elements are checked, and doubling the array still doubles the work.
• Worst, O(n): the target is last or missing, so every element is compared.
• Space, O(1): it only needs the current index.

When to use it, and when not to

• Use it when the data is not sorted and you do not want to pay to sort it.
• Use it for small arrays, or when you search only once.
• Use it when the data can only be read in order, such as a linked list.
• Avoid it when you search the same large array many times. Sorting once and using binary search is much cheaper.

Where linear search is used

Linear search is the default whenever nothing better is available, and in these places it is also the right choice:

• Lookups in built-in lists. The indexOf and includes methods of JavaScript arrays and the in operator and index method of Python lists scan from the front until they find a match. On a short list, a scan is cheaper than building and maintaining an index.
• Database table scans. When a query has no usable index, or has to read most of the rows anyway, a database reads the table row by row. PostgreSQL names this plan step a "Seq Scan". Reading in storage order is cheap because disks and caches favor sequential access.
• Chains inside a hash table. A hash table with chaining sends a key to one bucket, then walks that bucket's linked list with a linear search. The chains are short, so the scan stays fast.

Common mistake and edge cases

Related algorithms and variations

Knuth (section 6.1) describes a sentinel version: put a copy of the target after the last element, and the loop no longer has to test for the end of the array in every round. He also covers self-organizing lists, which move a found element toward the front so that frequent targets are found sooner.

When the data is sorted, binary search replaces the scan with halving, and linear search vs binary search shows the operation counts side by side. When the same collection is searched often by key, a hash table jumps straight to one bucket and takes O(1) time on average.