Binary Search

How to recognize it

The obvious version — "find a target in a sorted array" — is easy to spot and rarely the actual interview question anymore. The version worth training for is binary search on the answer: the prompt asks for a minimum or maximum value satisfying some condition ("the smallest capacity that ships all packages within D days," "the maximum number of books each person can take so nobody waits too long"), and the array being searched is not the input at all — it's the space of possible answers.

The tell: the condition is monotonic. If capacity C works, every capacity greater than C also works. That single property — false, false, false, then true, true, true forever after — is what makes binary search valid, whether or not anything is literally sorted.

How the pattern works

Define a feasible(x) check that answers "does this candidate value satisfy the constraint." Binary search over the range of possible values, narrowing toward the boundary wherefeasible flips from false to true.

def min_capacity_to_ship(weights, days):
    def feasible(capacity):
        trips, current = 1, 0
        for w in weights:
            if current + w > capacity:
                trips += 1
                current = 0
            current += w
        return trips <= days

    left, right = max(weights), sum(weights)
    while left < right:
        mid = (left + right) // 2
        if feasible(mid):
            right = mid
        else:
            left = mid + 1
    return left

function minCapacityToShip(weights, days) {
  function feasible(capacity) {
    let trips = 1;
    let current = 0;
    for (const w of weights) {
      if (current + w > capacity) {
        trips++;
        current = 0;
      }
      current += w;
    }
    return trips <= days;
  }

  let left = Math.max(...weights);
  let right = weights.reduce((a, b) => a + b, 0);
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (feasible(mid)) right = mid;
    else left = mid + 1;
  }
  return left;
}

Say the monotonicity argument out loud before coding: "if capacity C ships everything in time, any larger capacity also does — so I can binary search for the smallest C that works." That sentence is the actual insight; the loop is just execution.

Common mistakes

• Writing mid instead of mid + 1/mid - 1 when narrowing, causing an infinite loop when left and right are adjacent
• Searching for the wrong boundary — confusing "smallest value that works" with "largest value that still fails," which flips which side you keep
• Assuming the array must be sorted, and missing binary-search-on-the-answer questions entirely because no array in the prompt looks sorted
• Not verifying the monotonicity assumption before committing to the approach — if the condition genuinely is not monotonic, binary search will silently give a wrong answer, not an error

Complexity

Binary search itself is O(log n) iterations, but the total complexity depends on the cost of feasible() at each step — if that check is O(n), as in the shipping example above, the total is O(n log n). Stating both numbers, and explicitly noting which one is the search and which is the per-step check, shows the interviewer you understand where the log factor actually comes from rather than reciting "binary search is log n" without the context. See Time & Space Complexity.