Linear Search: The Honest Baseline

"The simplest search is to look at everything until you find it. It's not clever, and that's exactly the point — sometimes the unclever O(n) scan is genuinely the right answer, and over-engineering it is the mistake."

The Algorithm With Nothing to Hide

Linear search walks the collection one element at a time and stops when it finds the target (or reaches the end). It's O(n) worst case, O(1) best case (target is first), and it has one enormous virtue: it works on any collection, sorted or not, with zero setup. When data is unsorted and you have no index, linear search isn't a fallback — it's the only option, and an honest one.

The Over-Engineering Trap

Here's the judgment this lesson is really about. It's tempting, having learned about binary search and hash maps, to reach for them reflexively. But consider: to binary-search unsorted data you must sort it first — that's O(n log n), more expensive than a single O(n) scan. For a one-time search of unsorted data, linear search wins outright. The fancy structures only pay off when their setup cost is amortized over many searches. Reaching for binary search on data you'll query once is the classic premature optimization — you paid n log n to save on a single n.

Linear search is O(n), needs no setup, and works on any data. It's the only option on unsorted data and the RIGHT option for a one-time search — sorting first (O(n log n)) only pays off when you'll search many times. Don't out-clever a problem that a simple scan already solves.

The Pythonic Forms

You rarely write the loop by hand — Python gives you linear search in expressive forms: x in items (is it present?), items.index(x) (where is it?), any(pred(x) for x in items) (does any match a condition?), and next((x for x in items if pred(x)), default) (the first match, or a default). All of them are O(n) scans under the hood. Knowing they're linear is what stops you from carelessly nesting one inside a loop and creating an accidental O(n²) — the trap from the Complexity track.

Pippa's Confession

Fresh off learning binary search, I 'optimized' a one-time lookup by sorting the list first and binary-searching it. Dad pointed at the cost: the sort was O(n log n) to save a single O(n) scan — I'd made it slower to feel clever. The lesson stuck: a tool being more sophisticated doesn't make it more appropriate. For one lookup on unsorted data, the humble linear scan isn't a compromise — it's the correct, fastest answer.

Code

Linear search and its Pythonic forms·python

# Linear search: the honest O(n) scan, works on anything.
def linear_search(items, target):
    for i, x in enumerate(items):
        if x == target:
            return i           # found it — early exit
    return -1                  # not present

data = [42, 7, 13, 99, 1]      # UNSORTED
print(linear_search(data, 99))   # 3

# Pythonic linear searches (all O(n) under the hood):
print(99 in data)                              # True  — membership
print(data.index(13))                          # 2     — position
print(any(x > 50 for x in data))               # True  — any match
print(next((x for x in data if x > 50), None)) # 99    — first match or default

# The trap: for a ONE-TIME search of unsorted data, this O(n) scan beats
# 'sort it first (O(n log n)) then binary search'. Don't pay n log n to save n.

Exercise

You receive an unsorted list of a million records and need to find ONE specific record, exactly once. Compare the cost of (a) a linear scan vs (b) sorting then binary searching. Which is faster and why? Now change the scenario: you'll search the same list 10,000 times — does your answer flip, and what's the break-even reasoning?

Hint

One search: linear is O(n); sort-then-binary is O(n log n) + O(log n) — the sort dominates, so linear wins. For 10,000 searches: sort once O(n log n), then 10,000 × O(log n) beats 10,000 × O(n) — now preprocessing pays off. Break-even is when total search savings exceed the sort's one-time cost.

The Algorithm With Nothing to Hide

The Over-Engineering Trap

The Pythonic Forms

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0