Linear Search

Linear search walks an unsorted sequence one element at a time, returning the first match. O(n) — the only option when the data is unsorted or a tree/hash isn't available.

Complexity

Best	Average	Worst	Space (Worst)
`Ω(1)`	`Θ(n)`	`O(n)`	`O(1)`

How it works

Iterate from index 0; compare each element to the target; return on the first match (or -1 / None if the loop finishes). Best case O(1) when the target is at the front; worst and average O(n).

Python implementation

def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1


print(linear_search([3, 1, 4, 1, 5, 9, 2, 6], 5))  # 4

# Pythonic equivalents:
arr = [3, 1, 4, 1, 5, 9, 2, 6]
print(arr.index(5))               # 4 — raises ValueError if absent
print(5 in arr)                   # True
print(next((i for i, x in enumerate(arr) if x > 4), -1))  # 4

Trade-offs

O(n) — fine for small or unsorted data; the only option without prior structure.
Cache-friendly: walks memory sequentially.
Use a hash set for O(1) membership when the data is reused.
list.index and the in operator do this in C — faster than a Python-level loop.

← Back to Algorithms