Linear search was the first algorithm I ever wrote without realizing I was writing an “algorithm” at all — it’s just checking each item one at a time until I find what I’m looking for, which is exactly how I’d search a stack of papers on my desk by hand. It’s often dismissed as “the boring one” once you learn binary search or hashing, but I’ve come to appreciate that understanding exactly when linear search is the right choice — and when it genuinely isn’t — is just as important as knowing fancier algorithms exist. Here’s the complete picture.
The Core Idea
Linear (or sequential) search checks each element of a collection, one at a time, from the beginning, until it either finds the target or reaches the end without finding it. Unlike binary search, it makes no assumptions about the data being sorted — it works on any iterable, in any order.
def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1
numbers = [4, 2, 9, 7, 1, 8, 3]
print(linear_search(numbers, 7)) # 3
print(linear_search(numbers, 100)) # -1
This is about as simple as an algorithm gets, but there’s real depth in the variations, edge cases, and performance considerations worth understanding.
Searching for Multiple Occurrences
If the target value might appear more than once, a single-result linear search isn’t enough — I need to collect every matching index.
def linear_search_all(arr, target):
indices = []
for index, value in enumerate(arr):
if value == target:
indices.append(index)
return indices
data = [3, 1, 4, 1, 5, 9, 1, 2, 6]
print(linear_search_all(data, 1)) # [1, 3, 6]
Searching With a Custom Condition
Linear search doesn’t need to check for exact equality — it generalizes naturally to any condition, which is one of its genuine strengths over more specialized algorithms like binary search.
def linear_search_condition(arr, predicate):
for index, value in enumerate(arr):
if predicate(value):
return index
return -1
people = [{"name": "Alice", "age": 30}, {"name": "Bob", "age": 17}, {"name": "Carol", "age": 45}]
first_minor_index = linear_search_condition(people, lambda p: p["age"] < 18)
print(first_minor_index) # 1
This flexibility is something binary search simply can’t offer without significant additional structure — binary search fundamentally relies on a sorted, ordered comparison, while linear search can check for literally any arbitrary condition on each element.
Recursive Implementation
def linear_search_recursive(arr, target, index=0):
if index >= len(arr):
return -1
if arr[index] == target:
return index
return linear_search_recursive(arr, target, index + 1)
numbers = [4, 2, 9, 7, 1, 8, 3]
print(linear_search_recursive(numbers, 1)) # 4
Just like with binary search, I’d avoid this recursive version for very large lists in Python specifically, since it consumes one stack frame per element checked and can hit Python’s recursion limit for large inputs — the iterative version is strictly preferable for anything beyond small, illustrative examples.
Using Python’s Built-In Tools Instead
For many everyday cases, I don’t actually write a linear search function myself — Python’s built-ins already do this internally and are implemented in optimized C, making them faster than an equivalent hand-written Python loop.
numbers = [4, 2, 9, 7, 1, 8, 3]
# The 'in' operator performs a linear search under the hood for lists
print(7 in numbers) # True
# .index() returns the position of the first match, or raises ValueError if absent
print(numbers.index(7)) # 3
try:
numbers.index(100)
except ValueError:
print("Not found")
# .count() effectively performs a full linear scan, counting matches
print([1, 1, 2, 3, 1].count(1)) # 3
I reach for these built-ins constantly in practice, and reserve writing my own linear search function for cases needing custom logic (like searching with a predicate, or returning all matching indices) that the built-ins don’t directly support.
Time and Space Complexity
Linear search runs in O(n) time in the worst case — if the target is the last element, or isn’t present at all, every single element must be checked. On average, assuming the target is equally likely to be at any position, it takes roughly n/2 comparisons. The best case is O(1), if the target happens to be the very first element checked.
import time
large_list = list(range(10_000_000))
start = time.perf_counter()
large_list.index(9_999_999) # worst case — last element
end = time.perf_counter()
print(f"Time: {end - start:.4f} seconds")
Space complexity is O(1) for the basic version (a constant number of variables regardless of input size), though the “collect all matches” variant uses O(k) additional space where k is the number of matches found.
Why Linear Search Is Sometimes the Right Choice (Not Just “The Slow One”)
It’s tempting to think of linear search as strictly inferior once you know binary search exists, but that’s an oversimplification. Linear search is the right — sometimes the only correct — choice when:
- The data isn’t sorted, and sorting it first would cost more (O(n log n)) than the savings from a single subsequent binary search would justify, especially if you’re only searching once.
- You need a custom condition rather than exact equality against a sorted key, which binary search fundamentally can’t support without extra structure.
- The dataset is small, where the constant-factor overhead of more complex algorithms and data structures (setting up a hash table, sorting an array) can actually make them slower in practice than a straightforward linear scan, despite the better asymptotic complexity.
- You’re searching a linked list or a stream of data you can only access sequentially, where random access (needed for binary search’s midpoint jumps) isn’t available at all.
import time
small_list = [5, 3, 8, 1, 9]
# For a list this small, linear search is plenty fast — sorting first would be wasted overhead
def contains(arr, target):
for item in arr:
if item == target:
return True
return False
print(contains(small_list, 8)) # True
Searching a Generator or Stream (Where Random Access Isn’t Available)
One place linear search genuinely shines is when the data isn’t fully available as a random-access structure at all — like reading through a large file line by line, or consuming an API response stream.
def search_in_stream(stream, target):
for index, item in enumerate(stream):
if item == target:
return index
return -1
def line_generator(filepath):
with open(filepath) as f:
for line in f:
yield line.strip()
# result = search_in_stream(line_generator("large_log_file.txt"), "ERROR: disk full")
Binary search simply isn’t applicable here at all, since it fundamentally requires jumping directly to arbitrary positions (like the midpoint of a range), which isn’t possible on a stream you can only read sequentially, one item at a time.
Real-World Applications
- Searching small or unsorted collections, where the overhead of sorting or building an index isn’t justified by a single search.
- Searching with custom predicates, like finding the first item matching a complex business rule rather than an exact value match.
- Streaming data processing, such as scanning through log files or network streams line by line, looking for a specific pattern or event.
- Fallback logic in hybrid search systems, where a fast index (like a hash table) is checked first, and a linear scan serves as a correctness-guaranteeing fallback for edge cases the index doesn’t cover.
- Educational contexts, since linear search is the natural first algorithm to teach the very concept of searching, complexity analysis, and the trade-offs that motivate more advanced algorithms.
Common Mistakes
Assuming linear search is always “the wrong choice.” For small datasets, unsorted data, custom conditions, or streaming access patterns, it’s often the correct and even the only viable choice — dismissing it out of hand is a mistake.
Forgetting to handle the “not found” case explicitly. Returning -1, None, or raising an exception are all valid design choices, but the function’s behavior needs to be clearly defined and documented for when the target isn’t present.
Reinventing in, .index(), or .count() unnecessarily for simple exact-match searches on lists, when Python’s built-ins already do exactly this, faster, since they’re implemented in C.
Using linear search on data you’ll search repeatedly without considering better alternatives. If the same collection will be searched hundreds or thousands of times, the one-time cost of sorting (for binary search) or building a set/dictionary (for O(1) average lookups) pays for itself very quickly.
Writing a deeply recursive linear search on very large inputs, risking Python’s recursion limit unnecessarily when the iterative version has no such constraint.
Debugging Tips
- Test explicitly with the target as the first element, the last element, and an element not present at all — these boundary cases catch the overwhelming majority of real bugs.
- If searching for floating-point values, remember that exact equality comparisons (
==) can behave unexpectedly due to floating-point precision — consider a tolerance-based comparison (abs(value - target) < epsilon) instead of exact equality when appropriate. - For custom predicate searches, test the predicate function in isolation first, separate from the search loop, to confirm it behaves as expected before combining the two.
Performance Considerations
- Linear search is O(n) regardless of data characteristics — this is both its main limitation and, in some contexts (unsorted or streaming data), its main advantage, since it requires no preprocessing at all.
- For repeated searches on the same static dataset, converting to a
setordictfor O(1) average-case membership testing is almost always worth the one-time conversion cost, unless the dataset is genuinely tiny. - Python’s built-in
in,.index(), and.count()operations on lists are implemented in C and will outperform an equivalent hand-written Python loop for simple exact-match searches — prefer them unless you need custom logic the built-ins don’t support.
FAQs
Is linear search ever faster than binary search in practice? For very small collections, yes — the constant-factor overhead of binary search’s bounds-checking logic can occasionally make it slightly slower than a simple scan on tiny inputs, though the difference is usually negligible either way at that scale.
Does linear search require sorted data? No — this is actually its key structural advantage over binary search. It works correctly on data in any order.
What’s the difference between in, .index(), and a custom linear search function? in returns a boolean (found or not), .index() returns the position of the first match (or raises an exception if absent), and a custom function gives you full control — like returning all matches, searching with a custom predicate, or returning a sentinel value like -1 instead of raising an exception.
When should I switch from linear search to a hash table (set/dict)? As soon as you expect to perform many repeated lookups against the same static (or slowly changing) collection — the O(1) average-case lookup of a set or dict pays for its setup cost very quickly under repeated use.
Summary
Linear search is the simplest search algorithm there is — checking each element in turn until a match is found or the collection is exhausted — and while its O(n) worst-case complexity makes it slower than binary search or hash-based lookups for large, static, sorted, or frequently-searched datasets, it remains genuinely the right tool for unsorted data, custom conditions, small collections, and sequential streams where random access isn’t even possible. Understanding exactly when to reach for it, rather than dismissing it as merely “the slow one,” is what separates a surface-level understanding of algorithms from real practical judgment.
References
- Python official documentation: Common Sequence Operations (
in,.index(),.count()) - Python official documentation:
itertoolsmodule, useful for building custom search/filter pipelines - Python official documentation: Generators and iterators for stream-based searching