Linear SearchLinear search

01Why it exists

Reach for it when you see:Unordered data, tiny data, a single lookup, stop at the first hit, not worth sorting or indexing first.

02The core idea

Linear search is the most direct search there is: start at the first element, compare each one against the target, return the position on a match, and report "not found" if the scan finishes without one. It demands nothing of the data — no sorted order, no extra space — and works on anything you can walk through one item at a time: an array, a linked list, the lines of a file.

The cost is O(n) time and O(1) extra space. Best case the first slot is a hit, at one comparison; worst case is n comparisons, when the target sits in the last slot or is absent; and if the target is present and equally likely to be anywhere, the average is (n+1)/2 comparisons, which is still O(n). That number is not the problem in itself — the question is how many times you pay it. One O(n) lookup is cheap; m lookups cost O(mn), and that is when it starts to pay to spend O(n log n) sorting in exchange for O(log n) per binary search, or O(n) building a hash table in exchange for O(1) on average. Optimising trades setup cost against query cost, and data you query once is not worth the trade.

The other thing people overlook is the constant factor. A linear scan's loop is about as simple as code gets, memory access is sequential, and both the CPU's branch predictor and its cache are happy about it. Below a few dozen elements it often beats a hash table outright, because it skips computing a hash and skips the random memory access. So "just scan it when it is small" is what real systems do, not laziness: Rust's standard-library BTreeMap, for instance, holds at most 11 keys per node and finds a key within a node by linear search.

Where the neighbouring tools take over: if the data is already sorted (and randomly accessible), go straight to binary search — it pays off even for a single lookup. If the data is unordered but will be queried repeatedly, sort it and binary search, or build a hash table. If it is unordered and queried once, or so small that building any structure fails to pay for itself, use linear search. And note that with no structure to exploit, the worst case really does have to inspect every slot before it can conclude the target is absent, so O(n) is a lower bound here, not sloppy code. The point of learning this one is not the algorithm but knowing when you do not need a better algorithm.

03The algorithm

1. 1Start at index 0, so i = 0.
2. 2While i < n, compare nums[i] with the target. On a match return i — that is the only successful exit.
3. 3Otherwise i += 1 and go back to the previous step.
4. 4If i reaches n (including an empty array, where n = 0 from the start), everything has been checked without a match, so return -1.
5. 5When you want every matching position, do not return early: collect each matching i into a list and return it after the full scan.

04Interactive demo

Search 10 unordered numbers for 46, then switch to 40, which is not there, and watch how many comparisons the worst case takes. The table underneath lists the worst-case comparison counts for linear and binary search at various n — with the caveat that binary search needs the data sorted first.

05Code

The basic version, a version that returns every matching position, and the sentinel trick that saves one bounds check per iteration. All three are O(n) time; they differ in what they return and how many comparisons happen inside the loop. At the end are the linear searches each language already ships: in and list.index in Python, std::find in C++.

# Linear search: scan from the front, return the index on a hit, -1 otherwise
def linear_search(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1


# Variant 1: return every position that satisfies a condition (passed in as a function)
# With an arbitrary predicate every element must be checked, so O(n) is already optimal
def find_all(items, pred):
    return [i for i, x in enumerate(items) if pred(x)]


# Variant 2: the sentinel. Park the target at the end so a hit is guaranteed,
# which saves one i < n bounds check per iteration of the loop
# This is a trick for languages like C; in Python it is usually slower than the for loop above
def sentinel_search(nums, target):
    n = len(nums)
    nums.append(target)                 # the sentinel (temporarily mutates nums)
    i = 0
    while nums[i] != target:
        i += 1
    nums.pop()                          # restore
    return i if i < n else -1           # stopped on the sentinel = it was never there


if __name__ == "__main__":
    data = [17, 4, 29, 8, 51, 23, 12, 46, 3, 35]
    print(linear_search(data, 46))                 # 7
    print(linear_search(data, 40))                 # -1
    print(find_all(data, lambda x: x % 2 == 0))    # [1, 3, 6, 7]
    print(sentinel_search(data, 46))               # 7
    print(sentinel_search(data, 40), len(data))    # -1 10 (sentinel already removed)
    # The built-in in and list.index are linear searches too; index raises ValueError on a miss
    print(40 in data, data.index(46))              # False 7

06Practice

• LeetCode 2057Smallest Index With Equal Value (find the first one, return -1 on a miss)Easy
• LeetCode 2108Find First Palindromic String in the Array (the condition is a function; stop on the first hit)Easy
• LeetCode 2942Find Words Containing Character (return every matching position)Easy
• LeetCode 1779Find Nearest Point That Has the Same X or Y CoordinateEasy
• LeetCode 1848Minimum Distance to the Target Element (search outward from start)Easy
• LeetCode 1Two Sum (first search linearly for each number's partner, then work out why a hash table is better)Easy