Searching — Linear Search

By the end of this lesson you can:

• Implement linear search three ways: find-first, find-all, count.
• Return both the index and the value when needed.
• Reason about best, worst and average case — for a list of N items.
• Identify when linear search is the right choice and when to reach for binary search instead.

Every in operator and every .index() call you've written is a linear search:

names = ["Aisyah", "Wei Jie", "Priya", "Iman"]

"Priya" in names           # Python walks the list until it finds Priya
names.index("Priya")       # Same walk; returns the index (2)

Today we write the algorithm by hand. Same logic, more control — return early on hit, handle the not-found case explicitly, count matches.

1 · Find-first — return the index, or -1

def find_first(lst, target):
    for i, item in enumerate(lst):
        if item == target:
            return i
    return -1


print(find_first(["a", "b", "c", "d"], "c"))    # 2
print(find_first(["a", "b", "c", "d"], "z"))    # -1

The canonical shape. enumerate gives index + value. return i exits the moment we hit. return -1 after the loop signals "not found".

2 · Find-all — collect every match

def find_all(lst, target):
    return [i for i, item in enumerate(lst) if item == target]


print(find_all([10, 20, 30, 20, 40, 20], 20))    # [1, 3, 5]
print(find_all([1, 2, 3], 99))                    # []

List comprehension over enumerate. No early exit — must scan everything to find all matches.

3 · Count occurrences

def count_of(lst, target):
    n = 0
    for item in lst:
        if item == target:
            n += 1
    return n

# Or more Pythonically:
def count_of_v2(lst, target):
    return sum(1 for item in lst if item == target)

Same loop shape. We're still doing O(n) work — full scan unavoidable.

The cases — best, worst, average

Best case      Target is the first item                 → 1 comparison
Worst case     Target is the last (or not present)      → N comparisons
Average case   Random position in a random list         → N/2 comparisons

Conclusion: linear search is O(n).
For N = 1,000,000, that's up to 1 million comparisons.

What if the items are objects?

Same shape — just compare a specific attribute or use a predicate.

heroes = [Hero("Aisyah", 100), Hero("Wei Jie", 80), Hero("Priya", 95)]

# By attribute
def find_by_name(heroes, name):
    for h in heroes:
        if h.name == name:
            return h
    return None

# By any predicate
def find_first_where(seq, predicate):
    for item in seq:
        if predicate(item):
            return item
    return None

# Find the first hero with HP < 90
weak = find_first_where(heroes, lambda h: h.hp < 90)
print(weak.name if weak else "none found")

The predicate version is the most general — works for anything you can express as a boolean condition.

Early-exit short-circuit · the built-in way

Python's next() with a generator expression gives you find-first in one line:

weak = next((h for h in heroes if h.hp < 90), None)
# Returns first match, or None if no match

Same logic as the loop version, far more compact. Use this for one-off finds in real code.

Let's measure linear search empirically — confirm it's O(n). Save as linear_bench.py:

# linear_bench.py — count comparisons; demonstrate O(n) behaviour

import random
import time

class CountingList:
    """Wraps a list, counts comparisons against its items."""
    def __init__(self, items):
        self.items = items
        self.comparisons = 0
    def __iter__(self):
        return iter(self.items)
    def __getitem__(self, i):
        self.comparisons += 1
        return self.items[i]
    def __len__(self):
        return len(self.items)


def linear_search(seq, target):
    """Find target. Returns index or -1."""
    for i in range(len(seq)):
        if seq[i] == target:
            return i
    return -1


# Test for sizes from 10k to 1m
for size in [10_000, 100_000, 1_000_000]:
    data = CountingList(list(range(size)))
    target = -1                         # not in list — worst case

    data.comparisons = 0
    start = time.perf_counter()
    linear_search(data, target)
    elapsed = time.perf_counter() - start

    print(f"  N = {size:>8}  comparisons = {data.comparisons:>8}  "
          f"time = {elapsed * 1000:.2f} ms")

Sample output

  N =    10000  comparisons =    10000  time =   1.32 ms
  N =   100000  comparisons =   100000  time =  12.15 ms
  N =  1000000  comparisons =  1000000  time = 121.05 ms

Read the diff

Comparisons grow exactly linearly with N. Time grows roughly the same — 10× more items = 10× more time. That's O(n). Tomorrow's binary search will do the same job in ~20 comparisons for a million items — exponentially fewer.

Linear search walks a sequence until it finds the target or runs out. Three flavours: find-first (early exit, return index), find-all (full scan, return list), count (full scan, return number). O(n) in the worst case — N comparisons for N items. in, .index(), and next() + generator are Python's built-in versions. Linear search is the right tool when the data isn't sorted, when you'll only search once, or when the list is small.