Python Linear Search

A linear search (also called a sequential search) is the simplest way to find a value inside a collection: you look at every element, one after another, starting from the beginning, until you either find a match or run out of elements to check. It doesn’t require the data to be sorted, which makes it the most flexible search technique and often the first tool you reach for when working with small or unordered lists. Understanding linear search deeply also builds the intuition you need for faster algorithms like binary search, since linear search is the baseline every other search strategy is compared against.

Overview / How It Works

Linear search walks through a sequence element by element, comparing each one to the target value using ==. If an element matches, the search stops and reports where the match was found (usually its index). If the loop finishes without a match, the search reports that the value isn’t present. There is no cleverness involved — no assumptions about ordering, no skipping ahead — which is exactly why it works on any iterable: a plain list, a tuple, a generator, or even a linked list if you were implementing one from scratch.

Because it inspects up to every element, linear search runs in O(n) time in the worst case and on average, where n is the number of elements. The best case is O(1), when the target happens to be the very first element. Space complexity is O(1) as well, since it only needs a counter/index and no extra data structures. Compare this to binary search, which runs in O(log n) time but requires the data to already be sorted — linear search trades speed for the freedom to work on unsorted data with zero preprocessing.

It’s worth knowing that Python’s built-in tools already do linear search for you in many situations. The in operator (x in some_list) and the list.index() method both scan a list from the start, element by element, at the C level. They’re faster in practice than a hand-written Python for loop because the comparison loop runs in optimized C rather than interpreted bytecode, but the underlying algorithm — and its O(n) complexity — is identical to what you’ll write yourself in this lesson. Writing your own linear_search() function still matters because real searches are rarely just “does this exact value exist” — you often need the index, the first match under a custom condition, every match, or a search over objects rather than plain values, none of which the built-ins hand you directly.

Syntax

The general shape of a linear search function looks like this:

def linear_search(sequence, target):
    for index, value in enumerate(sequence):
        if value == target:
            return index
    return -1

Part	Meaning
sequence	The list (or other iterable) to search through
target	The value you’re looking for
enumerate(sequence)	Produces (index, value) pairs so you can track position while iterating
value == target	The comparison that decides whether the current element is a match
return index	Exits immediately once a match is found (this is called short-circuiting)
return -1	A sentinel value returned only if the loop finishes without finding a match

Examples

Example 1: Basic Linear Search

def linear_search(items, target):
    for index, value in enumerate(items):
        if value == target:
            return index
    return -1


numbers = [4, 2, 9, 7, 5, 1]
result = linear_search(numbers, 7)
print(f"Index of 7: {result}")

result_missing = linear_search(numbers, 100)
print(f"Index of 100: {result_missing}")

Output:

Index of 7: 3
Index of 100: -1

The function scans numbers from left to right. It checks 4, then 2, then 9, then 7 — at that point value == target is true, so it returns the index 3 immediately without looking at the remaining elements. For 100, which never appears, the loop runs to completion and the function falls through to return -1.

Example 2: Finding All Matching Indices

def find_all_indices(items, target):
    return [index for index, value in enumerate(items) if value == target]


scores = [85, 92, 85, 70, 85, 60]
matches = find_all_indices(scores, 85)
print(f"Indices where 85 appears: {matches}")

if matches:
    print(f"Found {len(matches)} matches, first at index {matches[0]}")
else:
    print("No matches found")

Output:

Indices where 85 appears: [0, 2, 4]
Found 3 matches, first at index 0

A single-match linear search stops at the first hit, but sometimes you need every occurrence. This version doesn’t short-circuit — it’s still a linear scan (still O(n)), but instead of returning early it collects every index where the value matches using a list comprehension built on the same enumerate pattern.

Example 3: Linear Search Over Objects

students = [
    {"id": 101, "name": "Ava"},
    {"id": 102, "name": "Liam"},
    {"id": 103, "name": "Maya"},
]


def find_student(students, student_id):
    for student in students:
        if student["id"] == student_id:
            return student
    return None


target_id = 102
found = find_student(students, target_id)

if found is not None:
    print(f"Student {target_id}: {found['name']}")
else:
    print(f"No student with id {target_id}")

missing = find_student(students, 999)
print(f"Lookup for missing id: {missing}")

Output:

Student 102: Liam
Lookup for missing id: None

This is where hand-written linear search really earns its keep: the built-in in operator can’t search by a field of a dictionary, only by exact equality of a whole value. Here the search compares student["id"] against the target on each iteration and returns the whole matching dictionary, or None if nothing matches. Notice the sentinel changed from -1 to None because the “found value” is now a dictionary, not an index — -1 would be a confusing, and misleading, choice here.

How It Works Step by Step (Under the Hood)

Tracing Example 1 with numbers = [4, 2, 9, 7, 5, 1] and target = 7:

• index=0, value=4 → 4 == 7 is False, continue
• index=1, value=2 → False, continue
• index=2, value=9 → False, continue
• index=3, value=7 → True, return 3 immediately

The for loop is abandoned the instant return executes — Python doesn’t keep checking indices 4 and 5. This early exit is what makes the best case O(1): if the target were at index 0, only a single comparison would run. If the target isn’t present at all (or is the very last element), every element gets compared once, giving the O(n) worst case. An empty list is a degenerate case worth noticing too: enumerate([]) yields nothing, the loop body never executes, and the function falls straight through to return -1 without error.

It also helps to know what CPython does when you use in or list.index() instead of writing your own loop: both walk the underlying array pointer by pointer in C, doing the equivalent of PyObject_RichCompare on each element until a match or the end of the array. Same algorithm, same O(n) behavior, just implemented below the Python interpreter for speed. That’s why x in my_list is usually preferred when you only need a yes/no answer.

Common Mistakes

Mistake 1: Testing the Result with Truthiness Instead of Comparing to the Sentinel

def linear_search(items, target):
    for index, value in enumerate(items):
        if value == target:
            return index
    return -1


numbers = [10, 20, 30]
result = linear_search(numbers, 10)

if result:
    print("Found")
else:
    print("Not found")

Output:

Not found

This is wrong even though 10 is clearly in the list at index 0. The bug is if result: — in Python, 0 is falsy, so when a match is found at index 0, the truthiness check treats it the same as “not found.” Always compare explicitly against the sentinel value instead of relying on truthiness:

def linear_search(items, target):
    for index, value in enumerate(items):
        if value == target:
            return index
    return -1


numbers = [10, 20, 30]
result = linear_search(numbers, 10)

if result != -1:
    print("Found")
else:
    print("Not found")

Output:

Found

Mistake 2: Forgetting That list.index() Raises an Exception

Unlike a hand-written search that returns -1 for “not found,” the built-in list.index() method raises a ValueError when the target isn’t present:

numbers = [4, 2, 9, 7, 5, 1]
index = numbers.index(100)
print(index)

Running this raises ValueError: 100 is not in list and crashes the program if it isn’t handled. Wrap the call in a try/except block so a missing value is handled gracefully instead of crashing:

numbers = [4, 2, 9, 7, 5, 1]
try:
    index = numbers.index(100)
    print(f"Found at index {index}")
except ValueError:
    print("100 is not in the list")

Output:

100 is not in the list

Best Practices

• Use enumerate(sequence) instead of range(len(sequence)) when you need both the index and the value — it’s more readable and more Pythonic.
• If you only need a yes/no membership check, prefer the built-in in operator (target in items) over a hand-written loop — it does the same linear scan but faster, in C.
• Pick a sentinel that can never be confused with a real result (-1 for indices, None for objects) and always compare against it explicitly rather than relying on truthiness.
• Reach for linear search on small, unsorted, or one-off searches; if you’ll search the same collection many times, convert it to a set or dict once for O(1) average-case lookups instead of repeating an O(n) scan every time.
• If the data is sorted and stays sorted, use bisect (binary search) instead — O(log n) beats O(n) once the list is large.
• Keep the comparison logic (value == target, or a custom condition like student["id"] == student_id) as the only thing inside the loop’s if — don’t mix in unrelated side effects that make the search harder to reason about.
• Add type hints (def linear_search(items: list, target) -> int:) on utility search functions so callers know what to expect back.

Practice Exercises

• Exercise 1: Write a function last_index(items, target) that returns the index of the last occurrence of target in items (instead of the first), or -1 if it isn’t present. Hint: you can scan from the end, or scan forward and keep overwriting a stored result.
• Exercise 2: Write a function count_occurrences(items, target) that counts how many times target appears in items using your own loop (don’t use list.count()). For items = [1, 3, 3, 5, 3, 7] and target = 3, it should return 3.
• Exercise 3: Given products = [{"name": "Pen", "price": 2}, {"name": "Book", "price": 15}, {"name": "Eraser", "price": 1}], write find_cheaper_than(products, max_price) that returns the first product dictionary whose "price" is less than max_price, or None if none qualify.

Summary

• Linear search checks each element in order until it finds a match or reaches the end — it needs no sorting and works on any iterable.
• Time complexity is O(1) best case, O(n) worst and average case; space complexity is O(1).
• enumerate() is the idiomatic way to get both index and value while scanning.
• Always use an unambiguous sentinel (-1 or None) for “not found,” and compare against it explicitly — never rely on truthiness, since a valid result like index 0 is falsy.
• list.index() and in perform the same linear scan internally but raise ValueError (for index()) instead of returning a sentinel, so handle that with try/except when needed.
• For repeated lookups on the same data, a set or dict beats linear search; for one-off or unsorted searches, linear search is simple, correct, and hard to beat for clarity.