Binary search

Binary search finds something in sorted data by checking the middle and throwing away half of what's left. That gets you O(log n).

Nearly all the bugs are at the boundaries. A pattern you can rely on is finding the first position where something becomes true, using a half-open range:

def first_at_least(values, target):
    low, high = 0, len(values)
    while low < high:
        middle = (low + high) // 2
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle
    return low

You don't even need an array. You can binary search over possible answers, like the slowest speed that still finishes a job on time, as long as the condition flips from false to true just once.

• Look for sorted input, timestamps, or a yes/no question over a range.
• Be able to say what low and high mean at every step.
• Test it with nothing, with one element, and with a target that's out of range.

The slowest speed that still finishes on time

There are piles of bananas, like [3, 6, 7, 11], and you have 8 hours. Each hour you can eat up to k bananas from one pile. Find the smallest k that finishes everything in 8 hours.

1. There's no sorted array here, but there is a yes/no question: 'can I finish at speed k?' If yes for k, it's yes for anything faster. The answer flips once, which is all binary search needs.
2. The answer is somewhere between 1 and the biggest pile, 11. Eating faster than that doesn't help.
3. Checking one speed means adding up ceil(pile / k) hours for each pile, which is O(n).
4. Try the middle, k = 6: 1 + 1 + 2 + 2 = 6 hours. That works, so the answer is 6 or less.
5. Try k = 3: 1 + 2 + 3 + 4 = 10 hours. Too slow, so the answer is between 4 and 6.
6. Try k = 5: 1 + 2 + 2 + 3 = 8 hours, which works. Then k = 4: 1 + 2 + 2 + 3 = 8 hours, which also works. The range is down to one value, so the answer is 4.
7. That's O(n log m) where m is the biggest pile, versus O(n × m) for trying every speed.

Things interviewers tend to ask once you've brought this up.

How do you search a rotated sorted array?

At each middle, one half is still sorted. Check if the target falls in that sorted half's range and go there, otherwise go to the other half.

How do you find the first and last position of a value?

Run the 'first position where value ≥ x' search twice: once for x, and once for x + 1. The last position is one before the second result.

Why use low + (high - low) / 2?

In languages with fixed-size integers, low + high can overflow. It doesn't matter in Python, but it's worth mentioning.

Can you binary search on real numbers?

Yes. Stop when high - low is small enough, or run a fixed number of iterations, like 100.

• Mixing closed and half-open ranges, which causes infinite loops or skipped elements.
• Updating low = middle instead of middle + 1, which can loop forever.
• Not noticing a problem can be solved by binary searching the answer.
• Forgetting the empty input and not-found cases.
• Binary searching data that isn't sorted, or a condition that flips more than once.

• Heaps and priority queuesAlways have the smallest or largest item ready.
• Dynamic programmingSolve each subproblem once and reuse the answer.
• Graph traversal and shortest pathsBFS, DFS and Dijkstra, and when to use each.