Binary Search and Search-Space Reduction

TL;DR: Binary search halves the search space each step, giving O(log n) instead of O(n), and it works on anything monotonic, not just sorted arrays. The high-value skill is spotting that a problem is secretly monotonic (if answer x works, every larger answer also works) and binary-searching on the answer rather than the data. Most candidates lose points on the loop boundaries; a template with while lo < hi and a half-open interval terminates cleanly and dodges the classic off-by-one.

The core idea: halve the space

Binary search needs one property: a way to look at the middle and decide which half to discard. On a sorted array that is the comparison target < mid. More generally it is any monotonic predicate, a yes/no test that is false-false-false-then-true-true-true across the space. Once you have that, each step throws away half the candidates, so n elements take about log2(n) steps. A million entries is about 20 comparisons.

A template that actually terminates

The off-by-one bugs come from inconsistent interval conventions: is hi the last valid index or one past it, is mid ever re-examined, does the loop shrink every iteration. Pick one convention and hold it. The half-open [lo, hi) version below terminates because the interval strictly shrinks every step and ends when lo == hi.

def lower_bound(nums, target):
    lo, hi = 0, len(nums)          # half-open: hi is one past the end
    while lo < hi:
        mid = lo + (hi - lo) // 2  # avoids overflow in fixed-width ints
        if nums[mid] < target:
            lo = mid + 1           # mid is too small, discard it and left
        else:
            hi = mid               # mid may be the answer, keep it in range
    return lo                      # first index with nums[i] >= target

The two rules that prevent infinite loops: when you discard the left half you must move past mid (lo = mid + 1), and when you keep mid as a candidate you set hi = mid (not mid - 1) so the range still shrinks because mid < hi. Returning lo gives the insertion point, which generalizes to "first true" of any predicate.

Binary search on the answer

The technique that separates strong candidates: when the array is not the thing being searched, the answer is. If you can write a predicate feasible(x) that is monotonic in x, you can binary-search the answer range even with no sorted input. Classic example, "minimum ship capacity to deliver all packages in D days": larger capacity is always feasible if a smaller one was, so feasible is monotonic. Binary-search capacity between max(weights) and sum(weights); each check simulates the days in O(n).

def min_capacity(weights, days):
    def feasible(cap):
        d, load = 1, 0
        for w in weights:
            if load + w > cap:
                d += 1             # start a new day
                load = 0
            load += w
        return d <= days
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid               # mid works, try smaller
        else:
            lo = mid + 1           # mid too small
    return lo

The same shape solves "smallest divisor under a limit," "minimum time to finish," and Koko-eating-bananas style problems. Total cost is O(n log(range)). Recognizing the hidden monotonicity is the whole battle; the search itself is mechanical.

When it applies

Why interviewers probe this

Binary search screens for two things: clean boundary handling and the ability to see monotonic structure where it is not obvious. The strong-answer move is to state the monotonic predicate explicitly ("feasibility only increases with capacity, so I can binary-search it") before coding, and to name your interval convention so the boundaries are not guesswork. The held-back follow-up is "why does your loop terminate?" or "what does it return when the target is absent?" Answering with the shrinking-interval argument and the insertion-point semantics shows you understand the template rather than having memorized one variant.

Common misconceptions

• "Binary search only works on sorted arrays." It works on any monotonic predicate; binary-search-on-the-answer needs no sorted input at all.
• "mid = (lo + hi) / 2 is fine." In fixed-width integers that can overflow; use lo + (hi - lo) // 2. In Python overflow is a non-issue but the habit transfers.
• "lo <= hi with hi = mid - 1 is the only template." It works, but mixing it with hi = mid causes infinite loops; pick one convention and be consistent.
• "It is O(log n) so the predicate cost does not matter." When binary-searching the answer, each step runs the predicate, so the real cost is O(predicate * log(range)).

Key takeaways

• Binary search needs monotonicity, not sortedness; a false-then-true predicate is enough.
• Binary-search-on-the-answer turns optimization problems into a feasibility check over a numeric range, O(n log(range)).
• Pick one interval convention (half-open [lo, hi) is clean) and the off-by-one and termination bugs disappear.
• The cost is O(log n) searches, each as expensive as your predicate; account for both.