juniorSearching

What is the difference between linear and binary search?

Updated Feb 20, 2026

Short answer

Linear search checks each element in turn — O(n), works on any data in any order. Binary search halves a sorted range each step — O(log n), but requires sorted, randomly accessible data. The practical question is rarely which is faster in the abstract: it is whether you will search often enough to repay the O(n log n) cost of sorting first.

Deep explanation

LinearBinary
TimeO(n)O(log n)
Requires sorted inputnoyes
Requires random accessnoyes
Works on linked listsyesnot efficiently
Comparisons on 1,000,000 itemsup to 1,000,000about 20

The complexity gap is enormous — twenty comparisons against a million — which makes binary search look unconditionally better. It is not, for three reasons.

Sorting is not free. One search on unsorted data costs O(n) linearly, or O(n log n) to sort plus O(log n) to search. Sorting pays off only when amortised across many searches. The break-even is roughly log n searches.

Cache behaviour favours linear. A linear scan walks memory sequentially, which the prefetcher handles perfectly and the branch predictor learns. Binary search jumps around unpredictably, missing cache on nearly every probe. Below a few dozen elements linear scanning usually wins on wall-clock despite doing more comparisons — which is why real sort and search implementations switch to linear below a threshold.

Maintaining sorted order has a cost of its own. If the collection changes frequently, every insertion must preserve the ordering — O(n) for an array. A hash table sidesteps the whole question with O(1) average lookup and no ordering requirement, and is usually the better answer when you need membership tests rather than range queries.

So the decision tree is: need range queries or ordering → sorted array with binary search, or a balanced tree. Need pure membership → hash table. Searching once over unsorted data → linear scan.

Real-world example

Two searches over the same 1,000,000 records:

Python
# once, over unsorted data — linear wins outright
def find_once(records, key):
    for r in records:              # ~500,000 comparisons on average
        if r.key == key:
            return r


# many times — pay to sort once, then search cheaply
records.sort(key=lambda r: r.key)  # O(n log n), done once
import bisect
keys = [r.key for r in records]
def find_many(key):
    i = bisect.bisect_left(keys, key)   # ~20 comparisons per call
    return records[i] if i < len(keys) and keys[i] == key else None

At ten thousand lookups the sorted version is dramatically ahead; at one lookup the sort alone costs more than the entire linear scan.

Common mistakes

  • - Comparing the two purely on Big-O and ignoring the O(n log n) sorting prerequisite.
  • - Applying binary search to data that is not fully sorted — it returns a wrong answer silently rather than raising.
  • - Using binary search on tiny collections, where a linear scan is faster in practice due to cache and branch prediction.
  • - Re-sorting the collection before every search, which is worse than never sorting at all.
  • - Overlooking that a hash table beats both for plain membership testing, at O(1) with no ordering requirement.

Follow-up questions

  • How many searches justify sorting first?
  • When would you prefer a hash table to either?
  • Does binary search work on a rotated sorted array?
  • Why do real implementations fall back to linear scanning?

More Searching interview questions

View all →