Binary Search

Intuition: the "guess the number" game

A friend picks a number from 1 to 100. You say 50, they say "higher." You say 75, they say "lower." Every question cuts the options in half, so you can guess any number in 7 questions. That's binary search.

It works under one condition only: the data is sorted. Then a single comparison tells you which half holds the answer, and you can safely throw the other half away.

Classic search: the picture

We're looking for 9 in a sorted array. We keep two bounds, left and right, and look at the middle, mid.

Three steps instead of five. On a million elements, you'd need about 20 steps instead of a million.

The invariant: how to get the bounds right

Almost every binary search bug is about the bounds. To avoid them, commit to an invariant, a rule that holds at every step:

If the answer exists, it lies in the range [left, right], inclusive.

Every detail follows from that rule:

• Start: left = 0, right = n - 1, because the whole array is a candidate.
• Loop while left <= right: as long as the range isn't empty, there's somewhere to look. When left == right, exactly one candidate is left, and you have to check it too.
• Move left = mid + 1 / right = mid - 1: you've already checked mid itself, so you exclude it. If you write left = mid, the loop can hang forever.
• Middle mid = left + (right - left) / 2: writing (left + right) / 2 in Java, C++, and Go can overflow int on large indices. Python has no overflow, but it's better to keep one habit across all languages.

Tip: when in doubt, trace your code by hand on arrays of 1 and 2 elements. That catches 90% of bound errors.

Insert position (lower bound)

Often the question isn't "is the element there?" but "where should it go so the array stays sorted?" In other words, you need the first index where a[i] >= target.

Here a half-open range [left, right) is more convenient:

• start: left = 0, right = n. The answer can also be n if the element is larger than everything;
• loop while left < right;
• if a[mid] < target, the answer is to the right: left = mid + 1;
• otherwise mid might be the answer, so you keep it: right = mid.

The loop ends when left == right, and that's your answer. The main thing: don't mix the two styles in one piece of code. Pick either "<= with mid ± 1" or "< with right = mid" and stick with it all the way through.

Binary search on the answer

The most powerful technique in this chapter. Sometimes there's no array at all, but there's a question like "what's the smallest k that works?", and the check "is k enough?" is monotonic:

k	1	2	3	4	5	6
enough?	no	no	no	yes	yes	yes

If k is enough, any larger k is enough too. So the answers line up as "no-no-no-yes-yes", and you need to find the first "yes". It's the same lower bound, except instead of an array you have a function ok(k).

A template example: you have pages pages and T minutes, and each printer prints one page per minute. What's the minimum number of printers? The check: ok(k) = k * T >= pages. You could compute this one with a formula, but in an interview ok is usually more involved, for example a greedy pass over an array. The search itself stays the same.

The algorithm step by step:

1. Set bounds lo and hi where ok(hi) is guaranteed to be true.
2. Find the first k for which ok(k) is true.

Template

def binary_search(a, target):
    left, right = 0, len(a) - 1
    while left <= right:                  # answer in [left, right]
        mid = left + (right - left) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def lower_bound(a, target):
    left, right = 0, len(a)               # answer in [left, right)
    while left < right:
        mid = left + (right - left) // 2
        if a[mid] < target:
            left = mid + 1
        else:
            right = mid                   # mid may be the answer
    return left

def min_k(lo, hi, ok):
    # first k in [lo, hi] where ok(k) is true; ok(hi) must be True
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

# example: 100 pages, 30 minutes, how many printers?
print(min_k(1, 100, lambda k: k * 30 >= 100))  # 4

Complexity

Variant	Time	Memory
Classic / lower bound	O(log n)	O(1)
On the answer	O(log(hi − lo) · cost of ok)	O(1)

How it sounds in an interview

"The array is sorted, so I can throw away half of it at each step. That's binary search in O(log n). I keep the invariant that the answer lies in [left, right]. I compute the middle as left + (right - left) / 2 to avoid overflow."

For search on the answer: "The check 'is k enough' is monotonic: if k is enough, so is k+1. So I binary search over the range of possible answers for the smallest k that works."

Common mistakes

• Mixing the styles: writing while left < right together with right = mid - 1. One candidate ends up never being checked.
• left = mid when mid rounds down: on two elements you get an infinite loop.
• The wrong hi bound in search on the answer: ok(hi) has to be true, otherwise the result is meaningless.
• Overflow inside ok: compute products like k * T in long.
• Forgetting about sorting: on an unsorted array, binary search silently returns garbage.

Remember one phrase: "invariant + monotonicity." If you can name both, you have binary search under control.