Linear Search

Linear search (also called sequential search) is the simplest way to find a value inside a collection: start at the beginning and check each element, one at a time, until you find what you’re looking for or run out of elements. It doesn’t require the data to be sorted, doesn’t need any extra memory, and works on almost any sequence you can iterate over — a list, a tuple, a linked list, or even a file read line by line.

It’s rarely the fastest option for large or frequently-searched data, but understanding it deeply matters: it’s the baseline every other search algorithm is measured against, and in plenty of real situations — small lists, unsorted data, or a one-off search — it’s genuinely the right tool for the job.

Overview / How it works

Imagine you’re handed an unsorted stack of resumes and asked to find the one belonging to a specific candidate. You have no way to jump to the middle and rule out half the stack the way you could with a sorted phone book — the resumes aren’t in any particular order. So you do the only thing you can: pick up the first resume, check the name, and if it isn’t a match, move to the next one. You repeat this until you find the right resume or you reach the bottom of the stack with no match. That is exactly what linear search does to a list.

Formally, linear search walks through a sequence from index 0 to index n - 1, comparing each element to the target value. As soon as it finds a match it stops and reports where the match was found (usually the index). If it reaches the end of the sequence without finding a match, it reports that the value isn’t present, typically by returning -1 or None.

The key insight is that linear search makes no assumptions about the data. It doesn’t need the list to be sorted, doesn’t need random access (it works fine on a linked list, where you can only move forward one node at a time), and doesn’t need any preprocessing. That generality is exactly why it’s slower than more specialized algorithms like binary search: those algorithms buy speed by exploiting structure (like sortedness) that linear search doesn’t require and doesn’t use.

Variants

Linear search shows up in a few closely related forms: returning the index of the first match, returning a boolean for “does this exist at all,” or collecting the indices of every match. All of them share the same core loop — only what happens on a match (and whether the loop keeps going) differs.

Time and Space Complexity

Let n be the number of elements in the sequence being searched.

Case	Time Complexity	Why
Best case	O(1)	The target happens to be the very first element checked — only one comparison is needed.
Average case	O(n)	On random data the target is, on average, about halfway through the sequence, so roughly n/2 comparisons happen. Dropping the constant factor of 1/2 (per the Big-O rule of dropping constants) still gives O(n).
Worst case	O(n)	The target is the last element, or it isn’t present at all — every one of the n elements must be examined before the loop can conclude.

Space complexity is O(1) for the standard iterative version: it only needs a fixed handful of variables (a loop index, maybe a running result), regardless of how large the input is. If you instead write linear search recursively (checking one element, then recursing on the rest), each recursive call adds a frame to the call stack, so space becomes O(n) in the worst case — and because Python’s default recursion limit is around 1000, a naive recursive linear search can raise a RecursionError on a list with more than a few hundred elements. For that reason, the iterative version is almost always preferred in Python.

Examples

Example 1: Finding the index of a value

def linear_search(arr: list[int], target: int) -> int:
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1


numbers = [4, 2, 9, 7, 5, 1]
result = linear_search(numbers, 7)
print(result)

result2 = linear_search(numbers, 100)
print(result2)

Output:

3
-1

The loop uses enumerate(arr) to get both the index and the value on each pass, which is the idiomatic Python way to write this (cleaner and less error-prone than manually indexing with range(len(arr))). Searching for 7, the function checks index 0 (4, no match), index 1 (2, no match), index 2 (9, no match), and index 3 (7, match) — it returns 3 immediately without checking the rest of the list. Searching for 100, none of the six elements match, so the loop finishes and the function returns the sentinel value -1.

Example 2: Finding every occurrence

def find_all_indices(arr: list[int], target: int) -> list[int]:
    indices = []
    for index, value in enumerate(arr):
        if value == target:
            indices.append(index)
    return indices


scores = [85, 90, 85, 70, 85, 60]
matches = find_all_indices(scores, 85)
print(matches)
print(f"Found {len(matches)} matches at indices {matches}")

Output:

[0, 2, 4]
Found 3 matches at indices [0, 2, 4]

This variant can’t stop early on the first match, because it needs to find all of them — so it always runs the full O(n) pass regardless of how many matches exist. Walking through scores, index 0 is 85 (match, append 0), index 1 is 90 (no), index 2 is 85 (match, append 2), index 3 is 70 (no), index 4 is 85 (match, append 4), index 5 is 60 (no). The final list of indices is [0, 2, 4].

Example 3: A realistic lookup over records

from typing import Optional


def find_user_by_username(users: list[dict], username: str) -> Optional[dict]:
    for user in users:
        if user["username"] == username:
            return user
    return None


users = [
    {"username": "alice", "age": 30},
    {"username": "bob", "age": 25},
    {"username": "carol", "age": 35},
]

found = find_user_by_username(users, "bob")
print(found)

missing = find_user_by_username(users, "dave")
print(missing)

Output:

{'username': 'bob', 'age': 25}
None

This is the shape linear search takes in most real code: scanning a list of records (dictionaries, objects, database rows fetched into memory) for the one matching some condition, not just scanning plain numbers. The function checks each user’s "username" key in order; "bob" matches the second dictionary, so that dictionary is returned immediately. Searching for "dave" exhausts the whole list without a match, so the function falls through to return None.

How it works step by step

Trace linear_search([12, 45, 3, 78, 23, 56], 78) by hand, the way the interpreter would execute it:

• Index 0: arr[0] = 12. Is 12 == 78? No, keep going.
• Index 1: arr[1] = 45. Is 45 == 78? No, keep going.
• Index 2: arr[2] = 3. Is 3 == 78? No, keep going.
• Index 3: arr[3] = 78. Is 78 == 78? Yes — return 3 immediately.

Notice the loop never looks at indices 4 or 5 (23 and 56) at all: as soon as a match is found, the function returns and the remaining elements are simply never touched. That’s the early-exit behavior that makes the best case fast, even though the worst case (searching for 56, or for a value that isn’t in the list) still requires all six comparisons.

Common Mistakes

Mistake 1: An off-by-one loop bound that skips the last element

def linear_search_buggy(arr: list[int], target: int) -> int:
    # BUG: range(len(arr) - 1) never reaches the final index
    for i in range(len(arr) - 1):
        if arr[i] == target:
            return i
    return -1


data = [10, 20, 30]
print(linear_search_buggy(data, 30))

Output:

-1

This looks reasonable at a glance, but range(len(arr) - 1) on a 3-element list produces range(2), i.e. indices 0 and 1 only — index 2 (the last element, 30) is never checked. The function incorrectly reports 30 as missing even though it’s the last item in the list. The fix is to iterate over the full range, range(len(arr)), or better yet use enumerate(arr) so there’s no length arithmetic to get wrong in the first place:

def linear_search(arr: list[int], target: int) -> int:
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1


data = [10, 20, 30]
print(linear_search(data, 30))

Output:

2

Mistake 2: Mutating a list while iterating it by index

def remove_zeros_buggy(numbers: list[int]) -> list[int]:
    for i in range(len(numbers)):
        if numbers[i] == 0:
            numbers.pop(i)
    return numbers


data = [1, 0, 0, 2, 0, 3]
print(remove_zeros_buggy(data))

Output:

IndexError: list index out of range

range(len(numbers)) is computed once, up front, as range(6) — but every call to numbers.pop(i) shrinks the list by one. Popping index 1 (the first 0) shifts the second 0 into position 1, so the very next iteration (now checking index 2) skips right past it without noticing it’s a zero. Worse, because range(6) keeps counting up to 5 regardless of the list’s shrinking size, the loop eventually tries to access an index that no longer exists, raising IndexError: list index out of range. Whenever you need to remove items while scanning, don’t mutate the list you’re iterating over by index — build a new list instead:

def remove_zeros(numbers: list[int]) -> list[int]:
    return [value for value in numbers if value != 0]


data = [1, 0, 0, 2, 0, 3]
print(remove_zeros(data))

Output:

[1, 2, 3]

Best Practices

• Reach for linear search when the data is unsorted, small, or stored in a structure without random access (like a linked list) — sorting just to enable a faster search is often not worth the O(n log n) upfront cost for a single lookup.
• If the data is already sorted, use binary search (O(log n)) instead — it will always beat linear search on anything but tiny lists.
• If you’ll search the same collection many times, pay the one-time cost of building a set or dict so each lookup afterward is O(1) on average, instead of paying O(n) on every single search.
• For a simple membership check on a list, Python’s built-in in operator already performs a linear search internally, implemented in C — it’s typically faster than a hand-written Python loop for the same job, so prefer if target in arr when you don’t need the index.
• Use enumerate(arr) instead of manually indexing with range(len(arr)) — it’s harder to get the bounds wrong and it’s more readable.
• Return (or break) as soon as a match is found rather than continuing to scan with a “found” flag — it’s both clearer and faster in the common case.
• Never mutate a list by index while iterating over it; iterate over a copy, filter into a new list, or iterate in reverse if in-place removal is required.

Practice Exercises

1. Write find_max_index(arr: list[int]) -> int that uses a single linear scan (no built-in max() or sorting) to return the index of the largest value, returning the first such index if the maximum appears more than once. Hint: track a running best value and its index as you go, updating them only on a strict improvement.
2. Write contains_substring(words: list[str], fragment: str) -> bool that linearly scans a list of strings and returns True as soon as it finds a word containing fragment, or False if none do. This is a common warm-up question in coding interviews — try it with words = ["apple", "banana", "grape"] and fragment = "an"; it should return True (matched by "banana").
3. Modify the basic linear_search function so it also returns the number of comparisons it made before stopping. Run it on lists of increasing size (say, 10, 100, and 1000 elements) searching for a value that isn’t present, and confirm the comparison count grows linearly with the list size — this is a hands-on way to see O(n) behavior rather than just taking it on faith.

Summary

• Linear search checks each element in sequence until it finds the target or exhausts the sequence — it requires no sorting and no special data layout.
• Time complexity is O(1) best case, and O(n) average and worst case, because in the worst case every one of the n elements must be examined.
• Space complexity is O(1) for the standard iterative version; a recursive version costs O(n) stack space and can hit Python’s recursion limit on large inputs.
• Use enumerate() instead of manual range(len(...)) indexing to avoid off-by-one bugs, and never mutate a list by index while iterating over it.
• Linear search is the right choice for small or unsorted data, or data you’ll only search once; switch to binary search for sorted data, or to a set/dict for repeated lookups.