Skip to content

level 2 · Searching

Linear Search

Check every box until you find it. Simple, honest, and slow.

6 min 40 XP

what is it

Start here

You are looking for one number in a pile. Linear search does the obvious thing: start at the beginning and check every box, one at a time, until you find what you want or run out of boxes.

It is the first algorithm anyone invents on their own, and it is not stupid. It works on *any* list — sorted, unsorted, chaotic. It needs no setup. For a short list, it is genuinely the right answer.

Its weakness is simple: if the thing you want is at the far end, you touch every single item to get there. Double the list, double the work. That relationship — cost grows in step with size — is what O(n) means.

real-life analogy

Picture it

Looking for your friend in a cinema

The lights are down and you don't know where they're sitting. So you walk the rows and check every face. If they're in the back row, you have checked the entire cinema. There's no shortcut — because the seats are in no useful order.

interactive visualization

Watch it run

Type a list, then the number to hunt for.

  1. 42
    0
  2. 7
    1
  3. 19
    2
  4. 3
    3
  5. 88
    4
  6. 15
    5
  7. 61
    6

Looking for 15. Linear search is the honest, patient way: check every box from left to right until you find it.

step 01/8

  • comparing
  • found it
  • ruled out
1function linearSearch(a, target) {
2 for (let i = 0; i < a.length; i++) {
3 if (a[i] === target) {
4 return i;
5 }
6 }
7 return -1;
8}

variables right now

target
15
comparisons 0moves 0

the dry run · every step, in words

8 steps

complexity

What it costs

best case
O(1)
average
O(n)
worst case
O(n)
extra memory
O(1)

Best case: it's the very first box. Worst case: it's the last one, or not there at all — and you touched all n boxes to be sure.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Returning 0 when the value isn't found.

    0 is a real index — it means 'found at the front'. Use −1 (or null) for 'not here', so the two answers can't be confused.

  • Carrying on looping after you've already found it.

    Return the moment you find it. Otherwise you do the full worst-case work every single time, even on a lucky hit.

  • Reaching for linear search on a big, sorted list.

    If it's sorted, binary search will find it in a handful of looks instead of thousands. Sorted data is a gift — use it.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+40 XP

01A list has 1,000 items and the one you want is last. How many do you check?

02What does linear search require of the list?

03You double the size of the list. What happens to the worst-case work?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.