Search Algorithms

Linear Search

● Beginner ⏱ 5 min read search

Linear search (sequential search) scans every element in order until it finds the target or exhausts the collection. It works on any sequence — sorted or unsorted — and requires no preprocessing.

The Algorithm

Text

Input:  list [3, 1, 4, 1, 5, 9, 2, 6], target = 5
Step 1: compare 3 with 5 → no
Step 2: compare 1 with 5 → no
Step 3: compare 4 with 5 → no
Step 4: compare 1 with 5 → no
Step 5: compare 5 with 5 → YES → return index 4

Best case:  target at index 0 → O(1)
Worst case: target at end or missing → O(n)

Python Implementation

Python

# Return index of target, or -1 if not found
def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(linear_search(nums, 5))    # 4
print(linear_search(nums, 7))    # -1

# Python built-ins use linear search internally
print(5 in nums)                 # True  — O(n)
print(nums.index(5))             # 4     — O(n), raises ValueError if missing
print(nums.count(1))             # 2     — O(n), counts all occurrences

Variants

Python

# Find all occurrences
def find_all(arr, target):
    return [i for i, v in enumerate(arr) if v == target]

print(find_all([1, 2, 1, 3, 1], 1))   # [0, 2, 4]

# Search with a predicate (generalized linear search)
def find_first(arr, predicate):
    for i, val in enumerate(arr):
        if predicate(val):
            return i
    return -1

people = [{"name": "Alice", "age": 30}, {"name": "Bob", "age": 25}]
idx = find_first(people, lambda p: p["age"] < 28)
print(people[idx]["name"])   # Bob

# next() with a generator — Pythonic one-liner
first_even = next((x for x in [1, 3, 4, 7, 8] if x % 2 == 0), None)
print(first_even)   # 4

When to Use Linear Search

💡

Linear search is often the right choice

For small collections (n < ~50), linear search is faster than binary search in practice because it avoids the overhead of maintaining sorted order. Binary search only wins on large, already-sorted arrays.

Python

# Use linear search when:
# 1. The collection is unsorted and you search only once
#    (sorting costs O(n log n) — more than a single O(n) scan)
# 2. The collection is very small
# 3. You need all matches, not just the first
# 4. Elements don't support comparison ordering (e.g. complex objects)

# Use binary search (next guide) when:
# 1. The collection is large AND sorted
# 2. You will search the same collection many times
# 3. You need O(log n) guaranteed lookup speed

Complexity Table

Case	Time	Note
Best case	O(1)	Target is the first element
Average case	O(n/2) = O(n)	Target at middle on average
Worst case	O(n)	Target at end or not present
Space	O(1)	No extra memory needed