Linear Search

Linear search checks every element one by one from left to right until it finds the target or reaches the end. It requires no preprocessing, no sorting, no special structure — just scan through and check each element.

How it works

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i   # found — return index

    return -1   # not found


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

Finding all occurrences

Linear search can easily find every occurrence of a value, not just the first one:

def linear_search_all(arr, target):
    indices = []
    for i, val in enumerate(arr):
        if val == target:
            indices.append(i)
    return indices


arr = [3, 1, 4, 1, 5, 9, 2, 6, 1]
print(linear_search_all(arr, 1))   # [1, 3, 8]

When linear search is the right choice

Linear search looks inefficient — O(n) compared to O(log n) for binary search. But it is often the correct choice:

Unsorted data — binary search requires sorting first. Sorting costs O(n log n). If you only need to search once, linear search at O(n) is faster overall.

Small arrays — binary search has overhead from index calculations. For arrays under ~20 elements, linear search with its simple loop often wins in practice.

Linked lists — binary search needs O(1) random access. A linked list requires O(n) to reach the middle element, making binary search O(n log n) — worse than linear search.

Searching by condition — "find the first element greater than 100" or "find the last negative number." Binary search only works for exact comparisons on sorted data.

One-time search on large unsorted data — sort (O(n log n)) then binary search (O(log n)) costs more than a single O(n) linear scan.

Sentinel linear search

A small optimization — place the target at the end of the array as a "sentinel" so the loop never needs to check the array boundary. Reduces comparisons by half:

def sentinel_search(arr, target):
    n = len(arr)
    last = arr[n - 1]         # save last element
    arr[n - 1] = target       # place sentinel

    i = 0
    while arr[i] != target:   # no boundary check needed
        i += 1

    arr[n - 1] = last         # restore last element

    if i < n - 1 or arr[n - 1] == target:
        return i
    return -1

Complexity