How Linear Search Works
Scan every element in order, return the index on match, return -1 on miss. The lower bound for searching unsorted data.
What you will learn
- Why linear search is the only valid strategy for unsorted collections
- How enumerate() makes the iterative implementation a two-line loop body
- How the four doctests cover a first-position hit, last-position hit, interior hit, and miss
- How rec_linear_search encodes the same scan with two converging pointers on the call stack
- How the recursive bounds guard raises an exception on invalid low or high arguments
- Why the recursion base case checks both low and high in one call, halving depth compared to single-pointer recursion
- How the __main__ block formats hit and miss output differently using an f-string
Prerequisites
- Comfort reading Python for loops and the enumerate() built-in
- Familiarity with recursion and the call stack
- No prior knowledge of search algorithms required
The story behind linear search
Linear search has no single inventor because it predates algorithm theory: any person looking for a name in a list by reading from top to bottom is doing a linear search. Its place in computer science is as the lower bound for searching unsorted data. If you know nothing about the order of the elements, you cannot rule out any position until you check it, so the worst case is always O(n). Every comparison-based search algorithm that does better (binary search at O(log n), hash lookup at O(1)) requires a structural property that the data must satisfy, whether sorted order or a collision-free hash function.
Linear search is also the baseline for sentinel search, an optimization where the target value is appended to the end of the array before the scan begins. Because the sentinel guarantees a match, the loop needs no end-of-array check, removing one branch per iteration. Donald Knuth documented the sentinel trick in The Art of Computer Programming. The educational implementation here omits the sentinel for clarity, but the pattern shows up in standard library string-search functions in C. Linear search also anchors the linear scan at the end of jump search, which reduces the number of elements it must check by jumping in blocks first.
Module Docstring: The Simplest Search
searches/linear_search.py:1The module docstring names the algorithm and provides the single doctest invocation command, establishing this as a minimal two-function file.
The module docstring is the same shape as every other file in searches/: algorithm name, doctest invocation, manual run command. The absence of an algorithm URL here is notable. Most algorithm files in this repository link to a Wikipedia or paper source in the function docstring, but linear search predates algorithmic publications and the Wikipedia article adds little beyond a loop description. The file compensates by using the function docstring's four doctests as the complete spec. Two functions live in searches/linear_search.py: the iterative linear_search and the recursive rec_linear_search. Reading both shows how the same scan encodes as a for loop or as a shrinking-window recursion.
A minimal module docstring names the algorithm and gives both run commands. No URL reference here because linear search has no canonical paper.
"""
This is a pure Python implementation of the linear search algorithm.
For doctests run following command:
python3 -m doctest -v linear_search.py
For manual testing run:
python3 linear_search.py
"""linear_search: A Two-Line Loop Body
searches/linear_search.py:12enumerate() pairs each element with its index. The loop returns the index on match and -1 after the loop exits without finding the target.
The function is eleven lines including the docstring and five lines of actual code. The loop body is two lines: check the current element, return if it matches. enumerate(sequence) on line 30 pairs each item with its position, so there is no separate index counter variable or range(len(sequence)) pattern. The contribution checklist's requirement to sort collections before searching does not apply here: the docstring explicitly notes "sorting is not required for linear search," which is both the algorithm's weakness and its single advantage. The four doctests on lines 21 through 27 cover the same four contract points as searches/binary_search.py: hit at the first position, hit at the last position, interior hit, and a miss that returns -1.
Two loop lines do all the work. enumerate() avoids a separate index counter. The -1 return after the loop handles a clean miss.
def linear_search(sequence: list, target: int) -> int:
"""A pure Python implementation of a linear search algorithm
:param sequence: a collection with comparable items (sorting is not required for
linear search)
:param target: item value to search
:return: index of found item or -1 if item is not found
Examples:
>>> linear_search([0, 5, 7, 10, 15], 0)
0
>>> linear_search([0, 5, 7, 10, 15], 15)
4
>>> linear_search([0, 5, 7, 10, 15], 5)
1
>>> linear_search([0, 5, 7, 10, 15], 6)
-1
"""
for index, item in enumerate(sequence):
if item == target:
return index
return -1rec_linear_search: Signature and Doctest
searches/linear_search.py:36The recursive variant takes explicit low and high bounds. Four doctests match the iterative version's contract: first hit, last hit, interior hit, miss.
The recursive variant is a two-pointer search, not a single-pointer scan. The signature on line 36 adds low and high parameters that bound the active search window. Each recursive call advances low upward and retreats high downward simultaneously, checking both ends before recursing. Callers pass explicit bounds (the doctests use 0, 4 for a five-element sequence) so the first call sets the full window and subsequent calls shrink it. The four doctests use the same five-element list with a different order than the iterative examples, which tests that the algorithm handles non-monotone sequences correctly: the recursive variant does not require sorted input for the same reason the iterative one does not.
The recursive variant checks both low and high each call, halving the depth compared to a single-pointer recursion that only advances low.
def rec_linear_search(sequence: list, low: int, high: int, target: int) -> int:
"""
A pure Python implementation of a recursive linear search algorithm
:param sequence: a collection with comparable items (as sorted items not required
in Linear Search)
:param low: Lower bound of the array
:param high: Higher bound of the array
:param target: The element to be found
:return: Index of the key or -1 if key not found
Examples:
>>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, 0)
0
>>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, 700)
4
>>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, 30)
1
>>> rec_linear_search([0, 30, 500, 100, 700], 0, 4, -6)
-1
"""Recursive Guards and the Base Case
searches/linear_search.py:57Three guards handle invalid bounds, exhausted window, and both ends matching before recursing. The tail call shrinks the window from both sides.
Five lines execute before the recursive call, and each one is a distinct contract check. Line 57 validates that both bounds are within range, raising an exception on the first invalid call rather than producing a silent wrong answer. Line 59 is the exhausted-window base case: when high falls below low, every position has been visited and the target is absent. Lines 61 and 63 check the current low and high positions respectively before recursing; because the function moves both pointers each call, missing either check would skip the element at that end on the next iteration. Line 65 is the single recursive call, passing low + 1 and high - 1 to shrink the window by two positions per frame. The recursion depth is therefore roughly n / 2, not n.
Checking both ends before recursing and advancing both pointers per call means the recursion depth is n / 2. The bounds guard prevents silent bad-index reads.
if not (0 <= high < len(sequence) and 0 <= low < len(sequence)):
raise Exception("Invalid upper or lower bound!")
if high < low:
return -1
if sequence[low] == target:
return low
if sequence[high] == target:
return high
return rec_linear_search(sequence, low + 1, high - 1, target)The __main__ Driver: Hit and Miss Formatting
searches/linear_search.py:68The __main__ block reads a sequence and a target from stdin, then formats the result differently for a hit versus a miss.
The driver shows one pattern this file handles differently from most other algorithm files: two distinct output formats depending on the result. A hit on line 75 prints the full linear_search(sequence, target) = result expression in a format that mimics a Python REPL evaluation, which makes the output self-explanatory without context. A miss on line 77 prints a plain sentence. The item.strip() call inside the list comprehension on line 70 handles whitespace around each token after the split, complementing the outer .strip() on the raw input that the contribution guide requires. This driver exercises only the iterative linear_search, not the recursive variant; a contributor testing rec_linear_search would call it from the Python REPL with explicit bounds.
The hit output mimics a REPL evaluation; the miss output is a plain sentence. Both require stripping whitespace from the input tokens to parse int() cleanly.
if __name__ == "__main__":
user_input = input("Enter numbers separated by comma:\n").strip()
sequence = [int(item.strip()) for item in user_input.split(",")]
target = int(input("Enter a single number to be found in the list:\n").strip())
result = linear_search(sequence, target)
if result != -1:
print(f"linear_search({sequence}, {target}) = {result}")
else:
print(f"{target} was not found in {sequence}")You've walked through 5 key areas of the The Algorithms - Python codebase.
Continue: How Binary Search Works → Browse all projectsCreate code tours for your project
Intraview lets AI create interactive walkthroughs of any codebase. Install the free VS Code extension and generate your first tour in minutes.
Install Intraview Free