Searching

Searching is the question "is this value here, and if so where," and the entire topic is a lesson in what one extra fact about your data — that it's sorted — buys you. Linear search makes no assumptions and checks every element, one by one, until it either finds the target or runs out of elements: reliable, simple, and O(n). Binary search assumes sorted order and exploits it to eliminate half the remaining candidates on every comparison, giving O(log n). Interviewers care about this because the leap from "check everything" to "check smartly using a known invariant" is the same leap behind database indexes (a B-tree is binary search generalized to disk pages), autocomplete, and version-control bisection (git bisect is literally binary search over commit history to find which commit introduced a bug). The topic also has a second life beyond literal sorted arrays: "binary search on the answer," where you binary-search over a range of possible answers rather than over an array, which is one of the highest-leverage patterns for turning a slow brute-force problem into a fast one.

Deep Dive: Linear Search — the Baseline

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

Linear search's cost is exactly the position of the target: best case O(1) (it's the first element), worst case O(n) (it's last, or absent — you must exhaust every element to be sure). There is no cleverness possible here in general, because with no ordering guarantee, any unexamined element could be the target; skipping one is a correctness bug, not an optimization. That is precisely why it is still the right tool for unsorted data or a one-off scan of a small collection — the cost of *sorting first* (at best O(n log n)) is not worth paying if you're only going to search once, or if n is small enough that O(n) and O(log n) are practically indistinguishable.

The subtlety worth stating precisely in an interview: linear search's O(n) is worst-case and average-case both scale linearly (average case is n/2 comparisons for a present target, uniformly distributed — still Θ(n) asymptotically, just with a smaller constant).

Deep Dive: Binary Search — Halving the Search Space

Binary search is O(log n) because each comparison doesn't just rule out one element — it rules out an entire half of the remaining candidates at once, by using the sortedness guarantee: if arr[mid] < target, every index at or before mid is also less than target (sortedness propagates that fact without checking them individually), so the whole left half is provably not the answer. Halving n repeatedly until you reach 1 takes log₂(n) steps — that's the definition of a logarithm. This precondition is not optional: run binary search on unsorted data and the halving logic is simply wrong, because "arr[mid] < target" no longer tells you anything reliable about the discarded half.

Best case is O(1) (target is the very first mid checked); worst and average case are both O(log n) — there's no pathological input that makes binary search worse than log n on a sorted array, which is part of why it's such a dependable building block.

Deep Dive: The Low/Mid/High Update Logic, and Its Classic Bug

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

The three classic off-by-one bugs are: using lo < hi instead of lo <= hi (misses the case where the search space has exactly one element left, incorrectly reporting "not found" for a valid single-element range); forgetting the +1/-1 when narrowing (lo = mid or hi = mid instead of mid + 1/mid - 1), which can loop forever because the already-checked mid stays inside the range; and integer overflow on mid = (lo + hi) // 2 in languages with fixed-width integers when lo + hi exceeds the max int (Python doesn't have this problem, but Java/C++ interviewers will ask about it — the fix is mid = lo + (hi - lo) // 2).

The invariant to hold in your head while coding this: at every iteration, if the target exists, it is guaranteed to be somewhere in arr[lo..hi] inclusive. Every update must preserve that invariant exactly — narrowing too aggressively (skipping mid itself when it's still a valid candidate) or too conservatively (leaving an already-ruled-out index in range) breaks it.

Deep Dive: Binary Search on the Answer

def can_ship(weights, capacity, days):
    days_needed, load = 1, 0
    for w in weights:
        if load + w > capacity:
            days_needed += 1
            load = 0
        load += w
    return days_needed <= days

def min_capacity(weights, days):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_ship(weights, mid, days):
            hi = mid
        else:
            lo = mid + 1
    return lo

"Binary search on the answer" means: instead of searching for a value's position inside a sorted array, you search over the *space of possible answers* (here, every integer capacity from max(weights) to sum(weights)) for the boundary where a yes/no predicate flips. You recognize a problem needs this pattern when it asks for a minimum (or maximum) value satisfying some feasibility condition, and you can write a "given this candidate value, is it feasible?" check that runs in reasonable time and is provably monotonic — once true, always true for larger values (or the symmetric case for smaller). The array itself never has to be sorted, or even exist; what's sorted, implicitly, is the true/false outcome of the predicate across the answer range.

This turns an O(n · feasibility-check-cost) brute force (try every capacity from lo to hi one at a time) into O(log(range) · feasibility-check-cost) — the same halving logic as classic binary search, just applied to a different axis.

Key Pointers

• Linear search makes no assumptions and is O(n) worst/average case; it's correct on unsorted data and the right choice when data is small, unsorted, or searched only once.
• Binary search requires sorted data — its halving logic is unsound otherwise — and is O(log n) worst/average/best-adjacent (best case O(1), worst and average O(log n)).
• Each binary-search comparison eliminates half the remaining candidates because sortedness lets you infer the truth about a whole range from one comparison.
• The loop condition must be lo <= hi and narrowing must use mid + 1 / mid - 1 — reusing mid itself in the next range risks an infinite loop or a missed single-element case.
• If you must sort first just to binary search once, you've spent O(n log n) to save what a single O(n) linear scan would have cost — sorting only pays off when you'll search the same data many times.
• "Binary search on the answer" applies the same halving idea to a range of candidate answers with a monotonic feasibility predicate, not to a literal sorted array.
• Recognize a binary-search-on-the-answer problem by the phrase "minimum/maximum X such that condition holds" plus a feasibility check that's monotonic across X.
• In fixed-width-integer languages, compute mid as lo + (hi - lo) // 2 to avoid overflow on lo + hi; not an issue in Python, but an interview talking point.

How It Works

1. Linear search: start at index 0, compare each element to the target in order, return the index on a match, return "not found" after the last index.
2. Binary search setup: confirm (or sort) that the array is sorted; set lo = 0, hi = len(arr) - 1.
3. Loop while lo <= hi: compute mid = (lo + hi) // 2.
4. If arr[mid] == target, return mid — done.
5. If arr[mid] < target, the target (if present) must be to the right, so set lo = mid + 1.
6. Otherwise the target must be to the left, so set hi = mid - 1.
7. If the loop exits without a match (lo > hi), the target is not in the array.
8. For binary search on the answer: define lo/hi as the plausible bounds of the answer itself, write a monotonic is_feasible(candidate) predicate, and binary-search over the candidate range instead of over array indices, narrowing toward the smallest (or largest) feasible value.

Try It Yourself

Linear vs binary search on the same sorted array, counting actual comparisons, plus a binary-search-on-the-answer example (minimum ship capacity).

def linear_search(arr, target):
    steps = 0
    for i, v in enumerate(arr):
        steps += 1
        if v == target:
            return i, steps
    return -1, steps

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

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31]
print("array:", arr, "n =", len(arr))
for target in (27, 4):
    li, ls = linear_search(arr, target)
    bi, bs = binary_search(arr, target)
    print(f"target={target:>3}  linear-> index={li:>2} steps={ls:>2}   binary-> index={bi:>2} steps={bs}")

# binary search on the answer: smallest capacity to ship packages within `days` days
def can_ship(weights, capacity, days):
    days_needed = 1
    load = 0
    for w in weights:
        if load + w > capacity:
            days_needed += 1
            load = 0
        load += w
    return days_needed <= days

def min_capacity(weights, days):
    lo, hi = max(weights), sum(weights)
    steps = 0
    while lo < hi:
        steps += 1
        mid = (lo + hi) // 2
        if can_ship(weights, mid, days):
            hi = mid
        else:
            lo = mid + 1
    return lo, steps

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
cap, steps = min_capacity(weights, 5)
print(f"min capacity to ship {weights} in 5 days = {cap} (found in {steps} probes)")

# Output:
# array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31] n = 16
# target= 27  linear-> index=13 steps=14   binary-> index=13 steps=3
# target=  4  linear-> index=-1 steps=16   binary-> index=-1 steps=4
# min capacity to ship [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] in 5 days = 15 (found in 5 probes)

Common Mistakes & Interview Traps

• Running binary search on unsorted data — the halving logic silently produces wrong answers instead of erroring, which makes this bug easy to miss in a live interview.
• Using lo < hi instead of lo <= hi, which incorrectly reports "not found" when exactly one candidate element remains.
• Narrowing with lo = mid or hi = mid instead of mid + 1 / mid - 1, re-including an already-ruled-out index and risking an infinite loop.
• Forgetting that sorting first costs O(n log n) — if you're only going to search once, sorting purely to enable binary search is slower overall than one O(n) linear scan.
• Assuming "binary search on the answer" needs a literal array to search — it needs a monotonic feasibility predicate over a numeric range, nothing more.
• Not verifying monotonicity before reaching for binary-search-on-the-answer — if the feasibility predicate isn't monotonic (true, then false, then true again), halving the range can skip over a valid answer entirely.

Interview Q&A

Q: Why does binary search require sorted data?

A: Every step relies on inferring that an entire half of the array is definitively too small or too large based on a single comparison at mid. That inference is only valid if the ordering guarantees every element to one side is uniformly less than (or greater than) arr[mid] — on unsorted data arr[mid] < target tells you nothing about the other elements, so the halving logic can eliminate the actual target.

Q: Walk through why binary search is O(log n) — what's actually being cut in half each step?

A: The size of the remaining candidate range, hi - lo + 1, is exactly halved (rounding) on every iteration, because one comparison rules out either everything at or below mid or everything at or above mid. Halving a quantity repeatedly until it reaches 1 takes log₂(n) halvings by definition — that's why n=16 takes at most 4 comparisons and n=1,000,000 takes at most 20.

Q: What's the classic off-by-one bug in binary search and how do you avoid it?

A: The most common is narrowing the range with lo = mid or hi = mid instead of mid + 1/mid - 1 — since arr[mid] was already checked and ruled out, leaving it inside the next range can cause lo and hi to stop converging, looping forever. Avoid it by writing the loop invariant explicitly ("if the target exists, it's in arr[lo..hi] inclusive") and making sure every branch preserves it exactly, excluding the just-checked mid.

Q: What is "binary search on the answer," and how do you recognize a problem that needs it?

A: It's applying the halving idea to a range of candidate answers rather than array indices — you binary-search for the boundary where a monotonic "is this candidate feasible?" predicate flips from false to true. You recognize it from phrasing like "find the minimum/maximum value such that X holds," combined with being able to write an efficient feasibility check that's monotonic across the candidate range.

Q: When would linear search actually be the better choice over binary search?

A: When the data is unsorted and will only be searched once or a few times — sorting costs O(n log n) up front, so paying that just to enable O(log n) searches loses to a single O(n) linear scan unless you'll reuse the sorted order many times. It's also the right (only) choice when there's no total order to sort by, or the dataset is small enough that the constant-factor overhead of binary search's branching isn't worth it.

Follow-up: How many searches does it take before sorting-then-binary-searching beats repeated linear search?

A: Roughly, once total cost O(n log n) + k·O(log n) (sort once, then k binary searches) drops below k·O(n) (k linear searches), which happens once k is large enough relative to log n — for most real n this crossover happens at single or low double-digit numbers of repeated searches, so "will this data be searched more than a handful of times" is the practical question to ask.

Follow-up: How would binary search change if the array had duplicate values and you needed the *first* occurrence of the target?

A: Instead of returning immediately on arr[mid] == target, record the match and keep searching the left half (hi = mid - 1) to see if an earlier occurrence exists, only stopping when the range is exhausted. This is the standard "leftmost binary search" variant and is a common follow-up precisely because naive early-return code gives an arbitrary occurrence, not the first.

Follow-up: Can binary search be applied to a rotated sorted array, like [15,18,2,3,6,9]?

A: Yes — at each step, at least one half (lo..mid or mid..hi) is still guaranteed to be normally sorted even though the whole array isn't; you check which half is sorted by comparing its endpoints, then decide whether the target could lie in that sorted half or must be in the other, and recurse the same halving logic accordingly.

Trade-offs

Linear search is the right default whenever data is unsorted and will be searched rarely, whenever the collection is small enough that asymptotic differences don't matter in practice, or whenever maintaining sorted order would cost more than it saves (frequent insertions into the middle of a sorted array are themselves O(n) each, which can erase binary search's advantage if updates vastly outnumber lookups). Binary search wins decisively when the same sorted (or naturally monotonic) dataset is queried repeatedly — the O(n log n) sort is a one-time cost amortized across many O(log n) lookups. Neither is universally right for dynamic data with frequent inserts and searches; that's usually a sign to reach for a different structure entirely — a hash table for O(1) average lookup with no ordering, or a balanced BST / B-tree for ordered data that also needs efficient insertion, both covered on their own pages in this section.

PracticeSolve related problems in the 150 →