Binary Search on the Answer: Your DP Instinct Is Wrong

You see "minimum possible maximum" and your brain starts sketching a DP table. Your hand reaches for the memoization dict. Stop. Half those problems are binary search in disguise, and once you see the shape, you cannot unsee it.

The pattern: instead of searching a sorted array for a value, you search the space of possible answers for the smallest (or largest) one that satisfies a condition. The array might not be sorted at all. That is what makes this feel slippery until it clicks.

The One Idea Behind All of It

Here is the core question: is there a yes/no test that becomes permanently true once the answer crosses some threshold?

Think about shipping packages. You have a list of weights and need to ship everything in D days. If capacity 10 works, capacity 11 also works. Capacity 9 might not. There is a hard threshold, and below it the answer is "no", above it the answer is "yes". That threshold is what you are looking for.

The key property is monotonicity: if X is a valid answer, then X+1 is also valid (or X-1, depending on direction). This turns an optimization problem into a binary search. You do not try all possible capacities. You binary search them.

Two flavors:

Minimize over valid answers: find the smallest X where feasible(X) is True. You are hunting the left edge of a run of True values.
Maximize over valid answers: find the largest X where feasible(X) is True. You are hunting the right edge.

Five Signals Your Problem Needs Binary Search on the Answer

Most of these problems announce themselves. Look for these:

"Minimize the maximum" or "maximize the minimum." These phrases are dead giveaways. Any phrasing that asks for the optimal value of some quantity subject to a feasibility constraint belongs here.

Large answer range in the constraints. The problem says answers can be up to 10^9. There is no way to try each one. The constraint is telling you the intended complexity: O(log(max_answer) × check_cost).

The brute force is "try every possible X and check." When you sketch the brute force as: loop X from 1 to max, check if X is feasible, return first valid X, you are staring at a binary search pattern. The only question left is how to write feasible(X).

The check is easy but computing directly is hard. You can answer "can we ship in D days with capacity X?" in one pass. You cannot directly compute the minimum capacity. This asymmetry is the pattern's fingerprint.

Signal three, every time. When your instinct is a for loop from 0 to n, that is a binary search with extra steps.

Two Templates. Pick One.

Pick based on whether you want the first True or the last True.

# Find the MINIMUM X where feasible(X) is True
# Search space: [lo, hi] inclusive
def solve(lo: int, hi: int) -> int:
    ans = hi  # fallback
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            ans = mid
            hi = mid - 1  # try to go smaller
        else:
            lo = mid + 1  # mid too small, must go bigger
    return ans

# Find the MAXIMUM X where feasible(X) is True
def solve_max(lo: int, hi: int) -> int:
    ans = lo  # fallback
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            ans = mid
            lo = mid + 1  # try to go bigger
        else:
            hi = mid - 1  # mid too big, must go smaller
    return ans

Two rules you cannot break:

Use mid = lo + (hi - lo) // 2, not (lo + hi) // 2. When lo and hi are both near INT_MAX, their sum overflows a 32-bit integer. Java's Arrays binary search had this exact bug for nine years. Nine. Years.
Store ans and keep shrinking. Do not return early when feasible(mid) is True. You found a candidate, not necessarily the optimal one.

Your Bounds Are Probably Wrong

This is where people burn time in interviews. The bounds are not arbitrary. They encode what is actually possible.

The lower bound is the minimum feasible answer, not zero or one.

For ship packages, minimum capacity must be at least max(weights). If any single package weighs 50 units, capacity 49 is impossible regardless of days. Setting lo = 1 works but wastes iterations and signals you have not thought about the problem.

The upper bound is the worst-case answer, not "infinity".

If capacity equals sum(weights), you ship everything in one day. So hi = sum(weights). Setting hi = 10**18 "just to be safe" is the interviewer telling themselves you are not thinking.

Three canonical setups:

Problem	lo	hi
Min capacity to ship in D days	`max(weights)`	`sum(weights)`
Koko eating bananas (min speed)	`1`	`max(piles)`
Painter's partition (min time)	`max(boards)`	`sum(boards)`
Aggressive cows (max min distance)	`1`	`max(pos) - min(pos)`

The pattern: lower bound is the hardest single element, upper bound is the total.

The Check Function Bug You Will Hit Every Time

The feasibility function is almost always a greedy simulation. Scan through the input, accumulate, and count how many "slots" you need. If the count exceeds your budget, return False.

The bug lives in ceiling division. And it will bite you at least once before you respect it.

For Koko eating bananas at speed k, the time to finish a pile of size p is ceil(p / k). In Python, that is (p + k - 1) // k. Not p // k. Not p / k. Both undercount, and your check function silently returns True for speeds that are too slow. The test cases will not catch it on the easy inputs. They will catch it on the edge case worth the most points.

def feasible(speed: int, piles: list[int], h: int) -> bool:
    hours = 0
    for pile in piles:
        hours += (pile + speed - 1) // speed  # ceiling division
    return hours <= h

The same bug shows up in every problem where you are counting batches. Any time you divide and the remainder matters, use ceiling division.

Full Koko solution:

def minEatingSpeed(piles: list[int], h: int) -> int:
    lo, hi = 1, max(piles)
    ans = hi

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if sum((p + mid - 1) // mid for p in piles) <= h:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1

    return ans

Time complexity: O(n log(max(piles))). Binary search over speeds, linear scan per check.

Binary search fixing someone else's code: wholesome, timeless, and occasionally ruins a government app's deadline.

Same Pattern, Three Disguises

Painter's Partition (Split Array Largest Sum, LC 410)

Partition an array into at most k subarrays to minimize the maximum subarray sum. Binary search on the maximum sum X. Check: can we partition into at most k subarrays each summing to at most X? Greedily pack elements until adding the next would exceed X, then start a new subarray.

def splitArray(nums: list[int], k: int) -> int:
    def feasible(max_sum: int) -> bool:
        pieces, current = 1, 0
        for num in nums:
            if current + num > max_sum:
                pieces += 1
                current = 0
            current += num
        return pieces <= k

    lo, hi = max(nums), sum(nums)
    ans = hi
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

Magnetic Force Between Two Balls (LC 1552)

Place m balls in n positions to maximize the minimum distance between any two. Binary search on the minimum distance d. Check: can we place all m balls with every pair at least d apart? Greedy: place a ball at position[0], then advance to the earliest position at least d from the last placed ball.

This is "maximize the minimum", so when feasible(d) is True, try larger d.

def maxDistance(position: list[int], m: int) -> int:
    position.sort()

    def feasible(min_dist: int) -> bool:
        count, last = 1, position[0]
        for pos in position[1:]:
            if pos - last >= min_dist:
                count += 1
                last = pos
        return count >= m

    lo, hi = 1, position[-1] - position[0]
    ans = lo
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

Minimum Days to Make Bouquets (LC 1482)

Binary search on day d. Check: count bouquets of k consecutive bloomed flowers on that day. Return True if count >= m. Bounds: min(bloomDay) to max(bloomDay). One linear scan.

In all three cases, the check function is a single greedy pass. Binary search reduces the outer loop from O(range) to O(log(range)).

When the Answer Is a Float

Some problems ask for a real-valued answer: square root to six decimal places, smallest real-valued speed. Same pattern, different termination.

Do not loop until hi - lo < 1e-9. Run exactly 100 iterations. After 100 halvings the interval shrinks by 2^100, precise enough for any practical constraint, and it sidesteps floating-point convergence weirdness.

def sqrt_binary_search(n: float) -> float:
    lo, hi = 0.0, max(1.0, n)
    for _ in range(100):
        mid = (lo + hi) / 2
        if mid * mid <= n:
            lo = mid
        else:
            hi = mid
    return lo

Note: if n < 1, then sqrt(n) > n, so the upper bound must be at least 1.

Five Steps, Then You Code

The moment you recognize the shape, you have a procedure:

Ask: what am I optimizing over? That is the search space.
Set lo to the minimum possible answer, hi to the maximum. Think about why each bound holds.
Write feasible(mid). Almost always a greedy scan.
Watch for ceiling division.
Minimizing: feasible(mid) true means store and shrink hi. Maximizing: store and grow lo.

The hardest part is not the binary search. It is recognizing that the problem has a monotonic threshold at all, then writing a correct greedy check. Once those are in place, the binary search is mechanical.

Narrate the monotonicity out loud before you code: "If capacity X works, does X+1 also work? Yes, extra capacity only makes things easier." That sentence is the proof. If you can say it confidently, you can use the pattern.

SpaceComplexity runs voice-based DSA mock interviews where you narrate this kind of reasoning to an AI interviewer, scored on problem-solving and communication the same way a real loop would. Getting a pattern into spoken language is a different skill from recognizing it on paper.