Binary Search on Answer

The Intuition

Binary search on the answer is the same algorithm as binary search on an array, applied to a different search space. Instead of an index range over a sorted array, the search space is the range of possible numerical answers, and instead of comparing to a target value, the loop calls a feasibility function isFeasible(mid) that returns yes or no.

The technique requires two ingredients:

A bounded answer range. Pick lo and hi so the true answer lies inside [lo, hi]. Often lo = max(nums) and hi = sum(nums), or lo = 1 and hi = max(input).
A monotonic feasibility predicate. As the candidate value increases (or decreases), isFeasible flips from false to true exactly once and stays. Equivalently, the YES region is a contiguous suffix (or prefix) of the answer range.

Given those two, binary search finds the boundary in O(log V) feasibility checks, where V is the size of the answer range. Each feasibility check usually scans the input in O(n), giving total O(n log V).

Three problem shapes show up repeatedly:

Minimize the maximum. "Minimum capacity to ship packages in D days" (LC 1011), "minimum largest sum after splitting into m subarrays" (LC 410). isFeasible(cap) answers "is cap enough capacity?" Lower hi when feasible.
Maximize the minimum. "Maximum minimum distance between cows" (LC 1552), "maximum candy each child gets" (LC 2226). isFeasible(d) answers "can every group have at least d?" Raise lo when feasible.
Minimum value satisfying a count. "Minimum eating speed" (LC 875), "smallest divisor given a threshold" (LC 1283). The feasibility check counts something and compares to a target.

Writing the feasibility function correctly is the entire problem. The binary search wrapper is boilerplate; once isFeasible is right, the surrounding loop is six lines.

When to use

The problem asks you to minimize a maximum value or maximize a minimum value, and you can write a feasibility function that is monotonic over the candidate range. If a candidate value works, then all larger (or all smaller) values also work.

When NOT to use

Condition is not monotonic (no clear boundary), answer space is discrete and small (just try all), or need to find multiple answers not just the boundary.

Pattern Recognition

Find the minimum possible maximum... or Find the maximum possible minimum...The answer lies within a bounded numeric rangeYou can verify whether a specific candidate answer is valid in O(n) or similar timeThe feasibility function is monotonic: once it becomes true (or false), it stays that wayConstraints involve distributing items, scheduling tasks, or splitting arrays under a limit

Edge Cases

All elements are equal, making the answer trivially the element value itself
Only one element exists, so the answer is forced
The feasibility boundary sits at the very start or end of the search range
Large input values that require careful overflow handling when computing lo + (hi - lo) / 2
Floating-point variants where you need sufficient iterations for precision

Practice Problems

MediumKoko Eating Bananas

HardSplit Array Largest Sum

MediumCapacity to Ship Packages Within D Days

MediumMinimum Number of Days to Make M Bouquets

Key Points

•Binary search over the value space, not the index space
•Define a feasibility function that checks if a candidate answer is valid
•Identify the monotonic property: if x works, all values above (or below) also work
•Search boundaries are the minimum and maximum possible answer values
•Works when the problem asks to minimize the maximum or maximize the minimum

Code Template

def binary_search_on_answer(nums, condition_args):
    """Binary search on the answer (value space).
    Finds the minimum value that satisfies the condition."""

    def is_feasible(candidate):
        # Check whether 'candidate' is a valid answer.
        # This function must be monotonic:
        # if feasible(x) is True, then feasible(x+1) is also True.
        pass  # problem-specific logic

    lo, hi = min_possible, max_possible

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            hi = mid       # candidate works, try smaller
        else:
            lo = mid + 1   # candidate fails, need larger

    return lo

# Example: Koko eating bananas
def min_eating_speed(piles, h):
    """Find minimum speed k so Koko finishes in h hours."""
    import math

    def can_finish(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 - lo) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo

func binarySearchOnAnswer(nums []int, target int) int {
    // Binary search on the answer (value space).
    // Finds the minimum value that satisfies the condition.

    isFeasible := func(candidate int) bool {
        // Check whether 'candidate' is a valid answer.
        // Problem-specific logic goes here.
        return false
    }

    lo, hi := minPossible, maxPossible

    for lo < hi {
        mid := lo + (hi-lo)/2
        if isFeasible(mid) {
            hi = mid       // candidate works, try smaller
        } else {
            lo = mid + 1   // candidate fails, need larger
        }
    }

    return lo
}

// Example: Koko eating bananas
func minEatingSpeed(piles []int, h int) int {
    maxPile := 0
    for _, p := range piles {
        if p > maxPile {
            maxPile = p
        }
    }

    canFinish := func(k int) bool {
        hours := 0
        for _, p := range piles {
            hours += (p + k - 1) / k
        }
        return hours <= h
    }

    lo, hi := 1, maxPile
    for lo < hi {
        mid := lo + (hi-lo)/2
        if canFinish(mid) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}

public int binarySearchOnAnswer(int[] nums, int target) {
    // Binary search on the answer (value space).
    // Finds the minimum value that satisfies the condition.
    int lo = minPossible, hi = maxPossible;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isFeasible(mid)) {
            hi = mid;       // candidate works, try smaller
        } else {
            lo = mid + 1;   // candidate fails, need larger
        }
    }
    return lo;
}

// Example: Koko eating bananas
public int minEatingSpeed(int[] piles, int h) {
    int maxPile = 0;
    for (int p : piles) {
        maxPile = Math.max(maxPile, p);
    }

    int lo = 1, hi = maxPile;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int hours = 0;
        for (int p : piles) {
            hours += (p + mid - 1) / mid;
        }
        if (hours <= h) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

Common Mistakes

Setting incorrect search boundaries (lo and hi)
Getting the feasibility check logic inverted
Off-by-one errors when deciding between lo = mid vs lo = mid + 1
Forgetting that the feasibility function must be monotonic over the search space

Related Patterns

The Intuition

The technique requires two ingredients:

A bounded answer range. Pick lo and hi so the true answer lies inside [lo, hi]. Often lo = max(nums) and hi = sum(nums), or lo = 1 and hi = max(input).

A monotonic feasibility predicate. As the candidate value increases (or decreases), isFeasible flips from false to true exactly once and stays. Equivalently, the YES region is a contiguous suffix (or prefix) of the answer range.

Three problem shapes show up repeatedly:

Minimize the maximum. "Minimum capacity to ship packages in D days" (LC 1011), "minimum largest sum after splitting into m subarrays" (LC 410). isFeasible(cap) answers "is cap enough capacity?" Lower hi when feasible.

Maximize the minimum. "Maximum minimum distance between cows" (LC 1552), "maximum candy each child gets" (LC 2226). isFeasible(d) answers "can every group have at least d?" Raise lo when feasible.

Minimum value satisfying a count. "Minimum eating speed" (LC 875), "smallest divisor given a threshold" (LC 1283). The feasibility check counts something and compares to a target.

Writing the feasibility function correctly is the entire problem. The binary search wrapper is boilerplate; once isFeasible is right, the surrounding loop is six lines.

def binary_search_on_answer(nums, condition_args): """Binary search on the answer (value space). Finds the minimum value that satisfies the condition.""" def is_feasible(candidate): # Check whether 'candidate' is a valid answer. # This function must be monotonic: # if feasible(x) is True, then feasible(x+1) is also True. pass # problem-specific logic lo, hi = min_possible, max_possible while lo < hi: mid = lo + (hi - lo) // 2 if is_feasible(mid): hi = mid # candidate works, try smaller else: lo = mid + 1 # candidate fails, need larger return lo # Example: Koko eating bananas def min_eating_speed(piles, h): """Find minimum speed k so Koko finishes in h hours.""" import math def can_finish(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 - lo) // 2 if can_finish(mid): hi = mid else: lo = mid + 1 return lo