Binary Search & the Answer Space

Binary search is the purest example of the “halve the problem” idea. Given a sorted array, you find a value by repeatedly checking the middle and throwing away the half that cannot contain your target. Each comparison cuts the search space in two, so searching a million elements takes about 20 steps, not a million.

Step through it and watch the shaded range collapse. At every step you look at the midpoint and make a decision: if the midpoint is too small, the answer must be to its right, so discard everything up to and including mid. If it’s too big, discard everything from mid rightward. You never look at the discarded half again — that’s where the log n comes from.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1      # answer is in the right half
        else:
            hi = mid - 1      # answer is in the left half
    return -1                 # not found

The details that trip people up

Binary search is famous for being easy to describe and hard to write correctly. Three things cause almost every bug:

1. Loop condition. lo <= hi (not <) so that a single-element range is still examined.
2. Midpoint. In languages with fixed-width integers, (lo + hi) / 2 can overflow; lo + (hi - lo) / 2 is the safe form. (Python’s big ints make this moot, but interviewers still look for it.)
3. Shrinking correctly. Always move past mid (mid + 1 / mid - 1) so the range strictly shrinks. Forgetting this is the classic infinite loop.

Binary search on the answer, not the array

The deeper, senior-level insight: binary search doesn’t need an array at all. It needs a monotonic predicate — a yes/no question whose answer flips exactly once as you increase some value. Then you can binary-search for that flip point.

“What is the smallest ship capacity that lets me deliver all packages within D days?” As capacity increases, “can I finish in time?” goes from no to yes and never back. That monotonicity means you can binary-search the capacity — even though there’s no sorted array in sight.

This reframing — binary search on the answer space — turns a whole class of optimization problems (“minimize the maximum,” “find the smallest feasible X”) into O(n log range) solutions. Spotting the hidden monotonic predicate is the skill that separates a rote binary search from a genuinely strong answer.

When to reach for it

Reach for binary search when the data is sorted, or when you can phrase the problem as “find the boundary where a condition flips.” If you can define a feasible(x) check that is monotonic, you can almost always binary-search x.

Pattern recognition

Variations

Worked problems

The code changes less than the question. Spend your planning time defining the predicate and the boundary you want.

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

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

    left = lower_bound(target)
    if left == len(nums) or nums[left] != target:
        return [-1, -1]

    right = lower_bound(target + 1) - 1
    return [left, right]

def min_eating_speed(piles, h):
    def can_finish(speed):
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed
        return hours <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo