Binary Search on the Answer: An Interview Pattern for Min-Max Problems

Binary Search on the Answer: An Interview Pattern for Min-Max Problems

Most people learn binary search as "find a target in a sorted array." In interviews, a more powerful version shows up constantly: you don't search the array at all. You search over the range of possible answers, and for each guess you ask a simple yes/no question: "Is this answer good enough?"

This guide explains the binary search on the answer interview pattern: how to recognize it, how to structure the code, and how to explain why it works.

How to recognize it

Signals that point to this pattern:

Classic examples:

The key property: monotonicity

The pattern works when feasibility is monotonic. If a ship capacity of 15 works, then 16, 17, and every larger capacity also work. If 14 fails, everything smaller fails too. So the answers look like:

fail fail fail fail PASS PASS PASS PASS

Binary search finds the first PASS in O(log range) checks. Saying this out loud is the most important part of your explanation.

The template

def min_feasible(lo, hi, feasible):
    # smallest value in [lo, hi] for which feasible(value) is True
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid        # mid works; maybe something smaller works too
        else:
            lo = mid + 1    # mid fails; answer is larger
    return lo

For "maximize the minimum," flip it:

def max_feasible(lo, hi, feasible):
    while lo < hi:
        mid = (lo + hi + 1) // 2   # round up to avoid an infinite loop
        if feasible(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

The rounding detail in the second version is a classic source of infinite loops. Mentioning it shows care.

Worked example: ship packages within D days

Given package weights in order and a number of days, find the minimum ship capacity that ships everything in time.

Bounds:

Feasibility check: greedily load packages day by day; start a new day when the next package would exceed capacity.

def ship_within_days(weights, days):
    def feasible(cap):
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used += 1
                load = 0
            load += w
        return used <= days

    return min_feasible(max(weights), sum(weights), feasible)

Complexity: the check is O(n), and we run it O(log(sum − max)) times, so O(n log S) overall.

Worked example: maximize the minimum distance

Place k items at given positions to maximize the smallest gap between any two.

def max_min_distance(positions, k):
    positions.sort()

    def feasible(gap):
        count, last = 1, positions[0]
        for p in positions[1:]:
            if p - last >= gap:
                count += 1
                last = p
        return count >= k

    return max_feasible(0, positions[-1] - positions[0], feasible)

Talk track for the interview

  1. Reframe: "Instead of finding the best capacity directly, I'll guess a capacity and check if it works."
  2. Monotonicity: "If a capacity works, any larger one also works, so the feasible answers form a contiguous range."
  3. Bounds: "The answer is at least the max weight and at most the total."
  4. Check: "For a given guess, a greedy pass tells me how many days I need, in O(n)."
  5. Complexity: "O(n log S), where S is the size of the search range."

Common bugs

How it relates to other patterns

The feasibility check is often greedy, sometimes a BFS, sometimes a prefix sum. Binary search on the answer is the outer loop that wraps one of those. When you see "minimize the maximum," think: "What's the cheapest way to check one guess?"

Practice the reframe out loud

The hardest part of this pattern isn't the code. It's noticing the reframe under pressure and explaining it clearly. Luna Interview helps you practice talking through problems like this with a timer running, so the insight comes out calmly when it counts.

Work through the five classic problems above and say the talk track every time. After a week, "minimize the maximum" will trigger this pattern automatically.