Binary Search on Answer — When Monotonicity Breaks

Standard binary search finds a target in a sorted array in O(log n). But what if the problem is asking for a minimum or maximum value that satisfies some condition, and you can check any candidate in O(n)? That's binary search on answer. It turns a 'find the optimum' problem into a 'does this candidate work?' problem, as long as feasibility is monotone. You never store the array – you just evaluate condition(mid) for any mid in the implicit range. This is the technique behind problems like 'minimum eating speed', 'smallest divisor', and 'minimum days to make bouquets'. It's not a trick; it's a direct application of binary search logic to the answer domain.

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)).

When to Use Binary Search on Answer — A 4-Point Identification Checklist

Not every optimization problem is suitable for binary search on answer. Use this quick 4-point checklist before deciding:

1. Optimization over a numeric range: The problem asks for a minimum or maximum value (e.g., minimum speed, maximum possible profit). If the answer is a value in a contiguous range, binary search on answer is a candidate.
2. You can write a feasibility function: You must be able to answer 'can we achieve X?' for any candidate X, in polynomial time. This function converts the decision into a yes/no answer. If you cannot efficiently check feasibility, the technique won't work.
3. Monotonic feasibility: The feasibility function must be monotonic — meaning as X increases, the outcome either stays true or switches from false to true exactly once (or the reverse for max-search). Test this with a few points before committing. If the function oscillates, binary search on answer will fail.
4. O(log range) iterations are worth it: The feasibility function should be efficient enough that calling it ~log(range) times is acceptable. For example, if the range is 10^9 and feasibility is O(n), the total O(n * log(10^9)) is often fine. If feasibility is O(n^2), consider a different approach.

If all four points check out, binary search on answer is likely the right technique. If any are missing, look for alternative methods.

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.

Floating-Point Binary Search on Answer for Continuous Optimization

Binary search on answer also works for continuous (real-number) answer spaces, as long as the feasibility function is monotonic. Instead of while lo < hi, you use while hi - lo > epsilon where epsilon is the desired precision. The feasibility function must also handle floating point comparisons with a tolerance.

Example: Find the square root of a number (without using math.sqrt). The feasibility function: (mid * mid <= x). Since square root is monotonic, binary search works.

Example: Find the minimum radius of a circle to cover all points. Feasibility checks if a circle of radius r covers all points. Since larger radius always works, monotonicity holds.

Pitfall: Floating point precision can cause infinite loops if epsilon is too small or the feasibility function is not robust. Use a maximum iteration limit (e.g., 100 iterations) as a safety net.

Template: ``python def float_binary_search(lo, hi, epsilon=1e-7): while hi - lo > epsilon: mid = (lo + hi) / 2 if feasible(mid): hi = mid # or lo = mid for max-search else: lo = mid # or hi = mid for max-search return (lo + hi) / 2 `` The feasibility function must be monotonic over the continuous range. Test with boundary values.

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

C++ Implementation of Binary Search on Answer

The same algorithm works in C++ with careful integer division and type handling. The ceil division idiom (pile + speed - 1) / speed works because integer division truncates toward zero. For large ranges, prefer mid = lo + (hi - lo) / 2 to avoid overflow. The condition function is typically a lambda or separate function. Below is a C++ version of the Koko Eating Bananas problem and the Minimum Days to Make Bouquets problem.

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int minEatingSpeed(vector<int>& piles, int h) {
    auto canFinish = [&](int speed) {
        long long hours = 0;
        for (int p : piles)
            hours += (p + speed - 1) / speed;  // ceil division
        return hours <= h;
    };
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}

int minDays(vector<int>& bloomDay, int m, int k) {
    long long total = 1LL * m * k;
    if (bloomDay.size() < total) return -1;
    auto canMake = [&](int day) {
        int bouquets = 0, bloomed = 0;
        for (int bd : bloomDay) {
            if (bd <= day) {
                bloomed++;
                if (bloomed == k) {
                    bouquets++;
                    bloomed = 0;
                }
            } else {
                bloomed = 0;
            }
        }
        return bouquets >= m;
    };
    int lo = *min_element(bloomDay.begin(), bloomDay.end());
    int hi = *max_element(bloomDay.begin(), bloomDay.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canMake(mid))
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}

int main() {
    vector<int> piles = {3,6,7,11};
    cout << minEatingSpeed(piles, 8) << endl;  // 4
    vector<int> bloomDay = {1,10,3,10,2};
    cout << minDays(bloomDay, 3, 1) << endl;   // 3
    return 0;
}

Common Pitfalls and How to Avoid Them

Binary search on answer is elegant but fragile. The #1 mistake: assuming monotonicity without verifying. #2 mistake: off-by-one errors in the search loop, especially in max-search. #3 mistake: using floating point division instead of integer ceil division. Always test with the smallest and largest possible answers. A safe habit: after the loop, assert that condition(lo) is True and condition(lo-1) is False (if lo > min range). For max-search, assert condition(hi) is True and condition(hi+1) is False.

Off-by-One Boundary Pitfalls in Binary Search on Answer

Off-by-one errors are the most common implementation bugs in binary search on answer. They manifest as infinite loops or wrong answers by one unit. Here are two classic examples:

Example 1: Min-search with wrong lo update Wrong: lo = mid when condition is false (instead of lo = mid + 1). This can cause an infinite loop because mid might equal lo when the range shrinks to 1. For example, if lo=5, hi=6, mid=5, condition false, setting lo=5 never changes, infinite loop. Fix: always use lo = mid + 1 on false for min-search.

Example 2: Max-search with wrong hi update Wrong: hi = mid when condition is false (instead of hi = mid - 1). This can also cause an infinite loop or return a value that is too large. For max-search, the correct approach is: if condition(mid) true, set lo = mid; else set hi = mid - 1. The midpoint calculation must use mid = (lo + hi + 1) / 2 to avoid getting stuck when lo and hi are adjacent.

Fix: Always test your algorithm with a small manual example where you know the answer. Use assertions after the loop to check that condition(lo) is True (for min-search) and condition(lo-1) is False.

Classic Binary Search on Answer Problems (LeetCode)

The following LeetCode problems are excellent practice for mastering binary search on answer. Each involves a monotonic feasibility function and a numeric answer space.

1. LeetCode 875 – Koko Eating Bananas Problem: Koko can eat at speed k bananas per hour. Given piles, find minimum k to eat all in h hours. Approach: Binary search speed from 1 to max(piles). Feasibility: sum(ceil(pile/k)) <= h. Monotonic because faster speed always reduces total time.

2. LeetCode 1011 – Capacity To Ship Packages Within D Days Problem: Ship packages in order within D days. Find minimum ship capacity. Approach: Binary search capacity from max(weights) to sum(weights). Feasibility: simulate loading days, ensure days <= D. Monotonic because larger capacity never increases days.

3. LeetCode 1482 – Minimum Number of Days to Make m Bouquets Problem: Given bloomDay array, make m bouquets of k adjacent flowers. Find minimum days. Approach: Binary search days from min(bloomDay) to max(bloomDay). Feasibility: simulate blooming and count adjacent blooms. Monotonic because more days can only increase bouquets.

4. LeetCode 1283 – Find the Smallest Divisor Given a Threshold Problem: Find smallest divisor such that sum of ceil(nums[i]/div) <= threshold. Approach: Binary search divisor from 1 to max(nums). Feasibility: sum ceil division. Monotonic because larger divisor always reduces sum.

5. LeetCode 774 – Minimize Max Distance to Gas Station (premium, floating-point variant) Problem: Add k gas stations to minimize maximum distance between adjacent stations. Approach: Binary search on the maximum gap. Feasibility: count how many stations needed to ensure all gaps <= candidate. Monotonic because larger gaps require fewer stations.