Linear search

Prerequisites

• Arrays and zero-based indexing.
• A for loop with an early return.
• Big-O notation.

The analogy

How it works

Data requirement: none. The array can be in any order.

Start with one search by hand

Look for 9 in [7, 3, 9, 4], starting from the left. Guess first, then open "Check".

Finish the picture

Now search the same array for a number that isn't there.

• Search for 5. Predict: how many comparisons, and what is returned?
  Check

  All 4 elements are checked, none match, so it returns −1. A miss always costs $n$ comparisons.

• Search for 7. Predict: how many comparisons?
  Check

  Just 1, since 7 is at index 0. That's the best case.

The rule in plain words

Start at index 0. If the element equals the target, return its index. Otherwise move one step right.

If you pass the end of the array, the target isn't there: return −1.

The code

Read this code after you have done one search by hand. It will make more sense.

int linear_search(const int a[], int n, int x) {
    for (int i = 0; i < n; i++)
        if (a[i] == x) return i;     /* first match wins */
    return -1;                       /* checked everything: not found */
}

flowchart TD
  A["i = 0"] --> B{"i < n ?"}
  B -->|no| F["Return -1: not found"]
  B -->|yes| C{"a[i] == x ?"}
  C -->|yes| D["Return i"]
  C -->|no| E["i = i + 1"]
  E --> B
          

How fast is it?

A target at position $i$ (counting from 1) costs $i$ comparisons. Averaged over all $n$ positions:

Halving doesn't change the growth, so the average and worst cases are both $O(n)$.

Common mistakes

• Returning −1 inside the loop on the first mismatch, so only a[0] is ever checked.
• Looping with i <= n, which reads one element past the end.
• Sorting the array first "to search faster": sorting costs $O(n \log n)$, more than one linear search.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• It works on unsorted data because it never assumes anything about elements it hasn't checked.
• The worst case is $O(n)$ because a missing target can only be ruled out by checking all $n$ elements.
• The average successful search is $\frac{n+1}{2}$ comparisons because the target is, on average, halfway along.
• It returns the first match because it scans left to right and stops immediately.
• Extra space is $O(1)$ because it only keeps a loop index.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is linear search like looking for keys in your pockets?
   Sample answer

   With no order to the pockets, any of them could hold the keys, so you check them one by one until you find them or run out.

2. Walk through a search for 9 in [7, 3, 9, 4].
   Sample answer

   7 is not 9, 3 is not 9, 9 matches, so it returns index 2 after three comparisons.

3. Why does the code return −1 only after the loop, never inside it?

   A good answer says what one mismatch tells you.

   Sample answer

   One mismatch only rules out that one element. You can only say "not found" after every element has been checked.

4. So what is linear search, in one sentence?
   Sample answer

   It checks each element in order and returns the index of the first one equal to the target, or −1.

5. Why must an unsuccessful search check every element?

   A good answer mentions the missing order.

   Sample answer

   Without order, the elements you've seen say nothing about the rest. The target could always be in the next slot.

6. What are its best, average and worst cases?
   Sample answer

   Best $O(1)$ when the target is first, average $O(n)$ with about $\frac{n+1}{2}$ comparisons, worst $O(n)$. Extra space is $O(1)$.

7. When should you not use linear search?
   Sample answer

   When the data is sorted, or when you'll search the same big array many times. Then binary search, after a one-off sort if needed, is far faster.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the $\frac{n+1}{2}$ average formula and the cache details. I'd keep the pocket analogy, one search on a small array, and "works on anything, $O(n)$, use binary search if sorted".

External resources

• GeeksforGeeks: Linear search: an article with code in several languages.
• Wikipedia: Linear search: analysis and the sentinel variant.
• Khan Academy: Algorithms: an intro course that starts with searching.

Videos

• YouTube search: linear search vs binary search: pick a short comparison video.