Binary Search on Answer Technique

Standard binary search finds a target in a sorted array. Binary search on the answer is different — you binary search over the range of possible answers, and for each candidate answer you check whether it’s feasible. If the feasibility function is monotonic (all True then all False, or vice versa), binary search finds the boundary in O(log(range) × check).

The Pattern

Answer space:  [lo … hi]
For each mid = (lo + hi) // 2:
if feasible(mid):
record mid as a candidate
search for a better answer (move hi or lo)
else:
search the other half

The template for minimizing the answer:

def binary_search_on_answer(lo, hi, feasible):
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

For maximizing the answer, flip it:

def binary_search_on_answer_max(lo, hi, feasible):
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if feasible(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

Problem 1: Koko Eating Bananas (LeetCode 875)

Koko has n piles of bananas. She can eat at speed k bananas per hour (one pile per hour, even if it has fewer than k). Find the minimum k to finish all piles in h hours.

import math

def min_eating_speed(piles, h):
    def feasible(k):
        hours = sum(math.ceil(p / k) for p in piles)
        return hours <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(min_eating_speed([3, 6, 7, 11], 8))  # 4

Search space: lo = 1 (minimum speed), hi = max(piles) (eat any pile in one hour).

Feasibility: at speed k, total hours is Σ ceil(pile / k). If that’s ≤ h, the speed works.

Problem 2: Capacity to Ship Packages (LeetCode 1011)

Find the minimum ship capacity to ship all packages within days days, preserving order.

def ship_within_days(weights, days):
    def feasible(capacity):
        day_count = 1
        current_load = 0
        for w in weights:
            if current_load + w > capacity:
                day_count += 1
                current_load = 0
            current_load += w
        return day_count <= days

    lo = max(weights)
    hi = sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

print(ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))  # 15

Search space: lo = max(weights) (must carry the heaviest single package), hi = sum(weights) (ship everything in one day).

Problem 3: Split Array Largest Sum (LeetCode 410)

Split an array into k subarrays to minimize the largest subarray sum. This is the same structure — binary search on the maximum allowed sum.

def split_array(nums, k):
    def feasible(max_sum):
        splits = 1
        current = 0
        for n in nums:
            if current + n > max_sum:
                splits += 1
                current = 0
            current += n
        return splits <= k

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

print(split_array([7, 2, 5, 10, 8], 2))  # 18

How to Spot These Problems

Look for these clues:

1. “Minimize the maximum” or “maximize the minimum” — classic binary search on answer phrasing.
2. The brute-force answer range is bounded and ordered.
3. There’s a greedy way to check if a candidate answer works.
4. The feasibility check is monotonic: if answer x works, then x+1 also works (for minimization).

Defining the Search Space

Getting lo and hi right is crucial:

Complexity Analysis

The log factor is over the answer range, and the feasibility check is typically O(n).

Interview Tips

• State the search space bounds explicitly before coding — interviewers want to see you reason about lo and hi.
• Always verify the feasibility function is monotonic: “if k works, does k+1 also work?”
• Use lo < hi with hi = mid for minimize, and lo < hi with lo = mid (plus mid = (lo + hi + 1) // 2) for maximize. This avoids infinite loops.
• Common bug: setting lo too low. If capacity must be at least max(weights), starting at 0 wastes iterations and can break the check.
• The greedy feasibility check is usually straightforward — practice writing it quickly.