Skip to content
Tutorials Center
My learning

Topics

Lesson 72 of 225 ยท Searching

Linear Search

Learn linear search in Python: the algorithm step by step, early exit, the sentinel trick, searching objects, finding all matches, comparison counts and when it is enough.

Searching means answering the question "is this item in my data, and where?" The simplest possible answer is also the most general: look at the items one after another until you find it or run out. That is linear search (also called sequential search), and every programmer uses it hundreds of times without a second thought: Python's in operator on a list, list.index() and any() are all linear searches.

Linear search needs no preparation, works on any sequence, and handles unsorted data, linked lists and files you can only read front to back. Its weakness is speed: the cost grows in step with the data. In this lesson you will write it from scratch, count its comparisons, learn the sentinel trick, search objects by a field, and learn exactly when it is the right tool and when binary search or a hash table should replace it.

The algorithm

TEXT
target = 7
index:   0   1   2   3   4   5
data:  [ 4 | 9 | 2 | 7 | 5 | 1 ]
         x   x   x  FOUND at 3        (4 comparisons)

target = 8:  checks all 6 items, none match -> not found

In words:

  1. Start at the first item.
  2. Compare the current item with the target.
  3. If equal, stop and report its position.
  4. Otherwise move to the next item.
  5. If you run past the last item, the target is not there.
Python Linear search with a comparison counter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Returning -1 for "not found" is a convention borrowed from other languages. In Python, None is often cleaner because -1 is also a valid index (the last item!). Whatever you choose, document it, and never use the result as an index without checking.

Complexity

Case Comparisons When
Best 1 the target is the first item
Worst n the target is last or missing
Average (target present, equally likely anywhere) about (n + 1) / 2

So the time is O(n), and the extra space is O(1). If a miss is common, the worst case is the one you will see most often. Compare the best, worst and average cases lesson for how these differ.

Python Average cost measured by counting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The average for a present target is (n + 1) / 2, which is 5.5, 50.5 and 500.5 here. Ten times more data means ten times more work. That straight-line growth is what the "linear" in the name means.

Early exit and what to return

Linear search is naturally early exit: stop at the first match. Python already gives you several versions, so you rarely write the loop by hand for a plain list:

You want Use
Is it there? target in items
Where is the first one? items.index(target) (raises ValueError if missing)
How many? items.count(target)
Any item satisfying a condition? any(cond(x) for x in items)
The first item satisfying a condition next((x for x in items if cond(x)), None)
Python The built-in versions of linear search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Finding every match

Sometimes you want all positions, not the first. Then you cannot stop early, so the cost is always n comparisons, and the result is a list.

Python Find all positions, and the last position

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Searching objects by a field

Real data is rarely a list of bare numbers. You usually search records by one field. The loop is the same; only the comparison changes.

Python Searching records by a field

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If you look up by id over and over, build a dictionary once, {s.id: s for s in students}, and each lookup becomes O(1) on average. One linear pass to build it, then no more linear searches.

The sentinel trick

The plain loop does two checks per item: "have I run out?" and "is it the target?". The sentinel variant removes the first one. You place a copy of the target at the end of the list (the sentinel), so the search is guaranteed to stop. Afterwards you decide whether the match was real or only the sentinel.

TEXT
target = 8
[4, 9, 2, 7, 5, 1]  ->  [4, 9, 2, 7, 5, 1, 8]   (sentinel added)
scan until value == 8; stopped at index 6 == original length -> not found
Python Sentinel linear search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each step does about half the comparisons of the plain loop. The complexity is still O(n); the saving is a constant factor. In Python the gain is negligible (the interpreter's overhead dominates, and mutating the input is risky), but the idea matters in low-level languages and shows how to simplify loop conditions with an extra element. It is also not safe if other code reads the list at the same time, and it needs a non-empty list.

Linear search on other structures

Linear search is the only choice when the structure gives you no random access. On a linked list you walk node by node; you cannot jump to the middle. On a 2D grid you scan rows then columns (see matrices for a faster search when rows and columns are sorted).

Python Linear search in a linked list and a grid

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When is linear search enough?

Linear search is the right answer more often than beginners expect.

  • Small data. For 10 or 50 items, anything fancier costs more to set up than it saves.
  • Unsorted data searched once. Sorting costs O(n log n), more than a single O(n) scan. Sort (or index) only if you will search many times.
  • Data you can only stream (files, network, generators, linked lists).
  • Complex conditions ("first order older than 30 days and over $50") that no index can answer.

Choose something else when you search the same big data repeatedly:

Situation Better tool
Many exact lookups dict or set, O(1) average (dicts and sets)
Sorted data, many searches binary search, O(log n)
Prefix queries on strings trie

Rule of thumb: if you will search k times in n items, linear search costs O(k x n). Building a dictionary costs O(n) once and then O(1) per search, so for large k it wins quickly.

Common mistakes

  • Using the result -1 as an index. items[-1] is the last item, so a "not found" silently becomes a wrong answer.
  • Calling list.index() without handling ValueError.
  • Using in on a list inside a loop (for x in a: if x in b), which is O(n x m). Convert b to a set first.
  • Comparing floats with ==. Use math.isclose for approximate matches.
  • Searching a list for each of many keys, instead of building a dictionary once.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A target is present in a list of 1,000 distinct items, equally likely at any position. About how many comparisons does linear search need on average?

    On average you scan half of the list, (n + 1) / 2 = 500.5 comparisons.
  2. 2. What does the sentinel technique remove from the loop?

    A copy of the target at the end guarantees the loop stops, so the 'have I run out of items?' check is no longer needed on every step.
  3. 3. Why is returning -1 for 'not found' risky in Python?

    Negative indexes count from the end, so using -1 without checking returns the last element instead of failing.
  4. 4. You must look up 100,000 keys in a list of 100,000 items. What is best?

    Repeated linear searches cost O(n x k). One O(n) build followed by O(1) average lookups is far cheaper.
  5. 5. What is the worst-case time of linear search?

    When the target is last or missing, every one of the n items is compared.

Summary

  • Linear search checks items one by one until it finds the target or runs out: O(n) time, O(1) space.
  • Best case 1 comparison, worst case n, average about n / 2 when the target is present.
  • Python offers in, index, count, any and next(...) as built-in linear searches.
  • A sentinel removes the bounds check from the loop, a constant-factor trick that does not change O(n).
  • It works on unsorted data, linked lists and streams, and is perfectly good for small or one-off searches.
  • For repeated searches use a dict or set, or sort once and use binary search.

Next: Binary Search