Binary Search on Answer — Parametric Search Technique

What is Binary Search on Answer? — Plain English

Binary search on the answer (parametric search) solves optimization problems of the form 'find the minimum/maximum value X such that some condition is satisfied.' Instead of searching for X in an array, you binary search on the range of possible answers. The key requirement is monotonicity: if condition(X) is true, then condition(X+1) is also true (or false — the condition must be monotone). For example: 'what is the minimum number of days to make at least m bouquets?' If it is possible in d days, it is also possible in d+1 days (more time = more options). So binary search on the number of days, checking feasibility for each candidate.

How Binary Search on Answer Works — Step by Step

Template for 'find minimum X where condition(X) is true':

1. Determine the search range: lo = minimum possible answer, hi = maximum possible answer.
2. While lo < hi:
3. a. mid = (lo + hi) // 2.
4. b. If condition(mid) is True: hi = mid (answer might be mid or smaller).
5. c. If condition(mid) is False: lo = mid + 1 (need a larger answer).
6. Return lo (the smallest X where condition is True).

The condition function runs in O(n) or O(n log n), and binary search does O(log(answer_range)) iterations, giving total complexity O(n log(answer_range)).

Worked Example — Koko Eating Bananas

Piles=[3,6,7,11], h=8 hours. Minimum eating speed k such that Koko can eat all piles within h hours?

For speed k, time per pile = ceil(pile/k). Total time = sum(ceil(pile/k) for all piles).

Search range: lo=1, hi=max(piles)=11.

mid=6: ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2=6 <= 8. Condition True → hi=6. mid=3: ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4=10 > 8. False → lo=4. mid=5: 1+2+2+3=8 <= 8. True → hi=5. mid=4: 1+2+2+3=8 <= 8. True → hi=4. lo==hi==4. Answer: k=4.

Verification: speed=4: ceil(3/4)=1, ceil(6/4)=2, ceil(7/4)=2, ceil(11/4)=3. Total=8 hours. Correct.

Implementation

Binary search on answer uses the standard binary search template but the array being searched is the implicit range [lo, hi] of possible answers. The feasibility check (condition function) encapsulates the domain-specific logic. Keep the template consistent: for minimum answer, use hi=mid when condition is True; for maximum answer, use lo=mid when condition is True. Always verify the boundary conditions with small examples.

import math

def min_eating_speed(piles, h):
    """Koko eating bananas: minimum speed k."""
    def can_finish(speed):
        return sum(math.ceil(p / speed) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            hi = mid      # might be able to go slower
        else:
            lo = mid + 1  # need faster speed
    return lo

def min_days_bouquets(bloomDay, m, k):
    """Min days to make m bouquets of k adjacent flowers."""
    def can_make(day):
        bouquets = bloomed = 0
        for bd in bloomDay:
            if bd <= day:
                bloomed += 1
                if bloomed == k:
                    bouquets += 1
                    bloomed = 0
            else:
                bloomed = 0
        return bouquets >= m

    if len(bloomDay) < m * k:
        return -1
    lo, hi = min(bloomDay), max(bloomDay)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_make(mid): hi = mid
        else: lo = mid + 1
    return lo

print(min_eating_speed([3,6,7,11], 8))   # 4
print(min_days_bouquets([1,10,3,10,2], 3, 1))  # 3

Frequently Asked Questions