Binary Search

Classic search, boundary search, and binary search on the answer.

Binary search halves the search space at each step, giving O(log n). Most candidates know the classic version; interviews test the two variations that trip people up: boundary search and binary search on the answer.

When to use it

The input is sorted (or rotated sorted)
You can phrase the problem as "find the first/last position where a condition becomes true"
The answer lies in a numeric range and a candidate can be checked with a monotonic feasibility test ("can we finish with speed k?")
Constraints are huge (10⁹+) and you need O(log n)

The one template to remember

Find the first index where condition(i) is true, assuming the condition is false…false, true…true:

def first_true(lo, hi, condition):
    # searches [lo, hi); returns hi if no index satisfies the condition
    while lo < hi:
        mid = (lo + hi) // 2
        if condition(mid):
            hi = mid        # mid might be the answer; keep it
        else:
            lo = mid + 1    # mid is not the answer
    return lo

Every variant becomes a choice of condition:

First element ≥ target: condition = lambda i: nums[i] >= target
Last element ≤ target: first_true(0, n, lambda i: nums[i] > target) - 1
Insert position: same as "first ≥ target"

This form avoids most off-by-one bugs because the loop invariant is simple: the answer is always in [lo, hi].

Binary search on the answer

When asked for the minimum value that works (or maximum), and "works" is monotonic, binary search over the value range:

import math

def min_eating_speed(piles, h):
    def can_finish(k):
        return sum(math.ceil(p / k) for p in piles) <= h
    return first_true(1, max(piles) + 1, can_finish)

Signals: "minimum capacity", "smallest maximum", "least time such that…". The check is usually a greedy O(n) pass, giving O(n log range) overall.

Rotated sorted arrays

At any midpoint, one half is sorted. Check whether the target lies within the sorted half's range; if so, search there, otherwise search the other half.

Pitfalls

Infinite loops from lo = mid with mid = (lo + hi) // 2 — the template above avoids it
Integer overflow in other languages: use lo + (hi - lo) // 2
Forgetting to check that the returned index is in range and actually matches

[!TIP] Practice Search in Rotated Sorted Array · Minimum Eating Speed · Time-Based Key-Value Store