Binary Search vs Linear Search: One Condition Changes Everything

You have a sorted array of a million integers. You want to find 42. Linear search will look at up to a million elements. Binary search will look at at most twenty. Same array, same target, twenty versus a million operations. The trick costs you nothing extra. Except one thing: the array must be sorted.

That's the whole story. The binary search vs linear search decision reduces to one question: is the data sorted? Everything else is a consequence.

How Linear Search Works

Linear search is the default. No preconditions, no setup. No feelings. It starts at index zero, walks forward, and stops when it finds the target or falls off the end.

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Time complexity: O(n) worst and average case, O(1) best case (target is the first element). Space is O(1). It never lies to you. If the element exists, linear search finds it. If it doesn't, linear search also finds that out, the hard way.

The underrated property here is memory access pattern. Linear search walks the array sequentially, one element at a time, left to right. Modern CPUs have a hardware prefetcher that detects sequential stride access and pre-loads cache lines before you need them. Each 64-byte cache line holds sixteen 32-bit integers, so the prefetcher has your data ready before the loop iteration that needs it. Linear search is about as cache-friendly as an algorithm gets.

Modern compilers also auto-vectorize sequential scans using SIMD instructions (SSE, AVX). A single AVX2 instruction can compare eight 32-bit integers simultaneously. That doesn't change the theoretical complexity, but it meaningfully changes the constant factor. The CPU is doing your job eight elements at a time and not complaining about it.

How Binary Search Works

Binary search works on one insight: if an array is sorted, the middle element tells you which half to discard. If the target is less than the middle, it must be in the left half. If greater, the right half. Either way, half the array is gone after one comparison.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # safe: avoids integer overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Time complexity: O(log n) worst and average case, O(1) best case (target is the middle element on the first probe). Space is O(1) for this iterative version.

The O(log n) Proof

Don't just accept the bound. Watch it fall out.

Start with an array of n elements. Each iteration cuts the search space in half:

After 1 step:  n / 2   elements remain
After 2 steps: n / 4   elements remain
After k steps: n / 2^k elements remain

The algorithm terminates when one element remains: n / 2^k = 1, so 2^k = n, so k = log₂(n). That's the maximum number of iterations before the search space collapses to a single element.

Each probe eliminates half the remaining candidates. Four steps to search sixteen elements. Thirty steps to search a billion.

As a recurrence: T(n) = T(n/2) + O(1), with T(1) = O(1). By the Master Theorem (a=1, b=2, d=0, so a = b^d = 1, the balanced case), T(n) = O(n^0 · log n) = O(log n). The recurrence and the Master Theorem agree with the arithmetic. Every algorithm that halves its input per step lands here. O(log n) time complexity covers the broader pattern.

The Bug That Hid for Twenty Years

The midpoint calculation you'll see in textbooks:

mid = (lo + hi) // 2  # WRONG in languages with fixed-width integers

If lo and hi are both large, their sum overflows a 32-bit integer before the division. Jon Bentley published this version in Programming Pearls in 1986. Java's Arrays.binarySearch contained the same bug. Joshua Bloch discovered it in 2006 after it had lived in production for nine years.

Nine years in a production Java runtime. The bug was old enough to start third grade by the time someone caught it.

The fix: mid = lo + (hi - lo) // 2. Same mathematical value, no overflow. Python integers don't overflow, so this is only a concern in C, C++, Java, and other fixed-width integer languages. It still comes up in coding interviews. Know it.

When Linear Wins in Practice

For small arrays, linear search is often faster than binary search in wall-clock time, even though binary search runs fewer comparisons.

Two reasons.

Binary search's access pattern is pseudo-random. It jumps to the middle, then to a quarter, then to three-quarters. These jumps thrash cache. For a small array that fits entirely in L1 cache (a few hundred integers), cache thrashing isn't an issue. But for the first few probes on a large array, binary search almost guarantees a cache miss on every step.

Linear search also auto-vectorizes. A SIMD scan of sixteen elements at once against binary search's one element per iteration means the comparison-count advantage narrows significantly for small n.

Benchmarks on Intel Broadwell hardware show:

For n < ~64, SSE-vectorized linear search is faster than binary search
For n < ~256, linear search remains competitive in latency benchmarks
For n > 1,000, binary search wins decisively

Knuth noted on the MIX computer model that binary search only outperforms linear search with a sentinel when n > 44. The crossover is architecture-dependent, but the lesson holds: small sorted arrays don't need binary search.

Linear search starts fast thanks to SIMD and sequential cache access. Binary search starts with overhead from cache misses on each jump. They cross somewhere in the n=64 to n=256 range. After that, binary dominates.

Is Sorting First Worth It?

Sorting costs O(n log n). If you sort once and then search k times, your total cost is O(n log n + k log n). Compare that to k linear searches: O(kn).

Binary search on a pre-sorted array is worth it when:

n log n + k log n  <  k * n
n log n  <  k * (n - log n)
k  >  n log n / (n - log n)  ≈  log n   (for large n)

If you'll run more than O(log n) searches, sorting first pays off. For n = 1,000,000, log₂(n) ≈ 20. If you need twenty or more lookups, sort the array first.

If you're doing a single one-off search on an unsorted list: don't sort. Linear search at O(n) beats O(n log n) + O(log n). This seems obvious until you're in an interview and your brain helpfully suggests sorting everything as a warm-up habit.

Lower Bound, Upper Bound, and Answer-Space Search

Standard binary search answers "is the target present and where?" Two variants come up constantly in interview problems.

Lower bound (first occurrence >= target): Returns the leftmost position where you could insert the target without violating sorted order.

def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Upper bound (first occurrence > target): Returns the rightmost position where you could insert without violating order. Together, upper_bound(arr, x) - lower_bound(arr, x) gives the count of occurrences of x in O(log n).

C++ provides std::lower_bound and std::upper_bound. Python's bisect module gives bisect_left and bisect_right. These are the versions you should actually use in practice. The standard library implementations handle all the edge cases correctly, which is more than can be said for most interview-room binary search implementations.

A third extension goes beyond searching arrays entirely: binary search on the answer. When a problem asks "minimize the maximum" or "find the smallest k such that some condition holds," you can often binary search over the answer space directly, running a feasibility check at each midpoint. The array of values becomes a logical sorted sequence of true/false answers. That extension gets its own treatment.

Your Loop Invariant Controls Your Update Rule

Every binary search implementation has one deep decision: what does the loop maintain?

The while lo <= hi variant (the one above) maintains the invariant that if the target exists, it's within [lo, hi]. When lo > hi, the interval is empty, so the target isn't present.

The while lo < hi variant maintains that the target is within [lo, hi). The loop ends when the interval has one element. You check that element after the loop.

Neither is wrong. Mixing them is. Pick one convention, understand its invariant, and be consistent. The two main bugs in binary search implementations are both invariant violations: using lo < hi but updating hi = mid when the comparison says target is in the right half, or using lo <= hi but updating hi = mid when you need hi = mid - 1. These bugs account for a remarkable share of binary search failures in interviews, where the pressure of being watched makes "I know this" feel different from "I'm currently writing this correctly." Get the invariant right and the rest follows. The binary search off-by-one guide traces both bugs in detail.

Binary Search vs Linear Search: How to Choose

Three questions decide which search to use.

Follow the diamonds. The decision really does reduce to three questions answered in order.

Is the data sorted? If no: linear search. Done.
How many lookups? If one or a few: linear search is probably fine. If many: sort once, then binary search.
How large is the data? For n < ~100: consider linear search even if sorted (cache and SIMD effects). For n > 1,000: binary search wins decisively on sorted data.

Real systems show the same pattern. A DNS resolver caching a handful of entries uses linear scan. A database with millions of rows builds a B-tree index (generalized binary search). A compiler's symbol table uses a hash map for exact lookups but falls back to binary search on sorted arrays for range queries.

If you've ever called bisect.bisect_left in Python or Collections.binarySearch in Java, you've been using this tradeoff automatically. The standard libraries made the right call based on precondition guarantees you probably didn't think about.

Understanding why, not just which, is what makes these concepts stick. If you want to practice applying this decision under interview pressure, SpaceComplexity runs voice-based mock interviews where you have to explain your choice out loud, not just type it.

Quick Recap

Linear search: O(n) time, O(1) space, no preconditions, cache-friendly, auto-vectorizable
Binary search: O(log n) time, O(1) space (iterative), requires sorted input
O(log n) comes from repeatedly halving the search space: n/2^k = 1 gives k = log₂(n)
Midpoint overflow: use lo + (hi - lo) // 2, not (lo + hi) // 2
Linear wins in practice for n < ~100 due to cache and SIMD effects
Sort first if you'll run more than O(log n) searches; don't sort for a one-off lookup
Lower bound and upper bound extend binary search to range queries and duplicate handling
The invariant (lo <= hi vs lo < hi) determines your update rule; mixing them causes bugs