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.

Why Brute Force Is Your First Clue, Not Your Final Answer

Every binary search on answer problem starts with a brute force that screams "I can do better." The competitors show you the naive linear scan because it reveals the search space. That's the real trick — identifying the range of possible answers is the hard part, not the binary search itself.

Look at the integer square root problem: you iterate n from 0 to X, checking n² < X. That's O(X). For X = 10⁹, that's a billion iterations. Your laptop will heat up. Your interviewer will yawn.

The "random approach" competitors mention? Don't bother. That's just dressed-up brute force with extra instability. You're gambling on randomness instead of exploiting structure.

Here's the pattern: if you can write a isFeasible(mid) function that runs in polynomial time, and your answer space is bounded and monotonic, you've got a binary search candidate. The brute force shows you the bounds — 0 to X in this case — and the feasibility check is literally the condition n² < X.

The optimization is O(log X * cost of isFeasible). For X = 10⁹, that's about 30 calls instead of a billion. You don't need to be a genius to see which wins.

// io.thecodeforge — dsa tutorial

public class IntegerSquareRootBruteForce {
    // Find max n such that n² < X
    public static int findMaxN(int x) {
        int answer = 0;
        for (int n = 1; n < x; n++) {
            if ((long) n * n < x) {
                answer = n;
            } else {
                break; // Once n² exceeds X, we're done
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        int x = 101;
        int result = findMaxN(x);
        System.out.println("Max n for X=" + x + " is: " + result);
        // Expected: 10 (since 10²=100 < 101, 11²=121 > 101)
    }
}

The isFeasible() Function — Your Only Real Leverage

Binary search on answer lives or dies on the quality of your isFeasible(mid) function. Get this wrong and you're binary searching into a brick wall. Get it right, and you can solve anything from book allocation to aggressive cows to Koko's bananas.

Competitors gloss over this, but here's the truth: the feasibility check is where the problem-specific logic lives. The binary search is just scaffolding. You can copy-paste the loop from any textbook. The canAllocate() or canFinish() function is where you earn your salary.

Here's the pattern from the integer square root: isFeasible(mid) returns mid² < X. Monotonic? Yes — as mid increases, mid² increases monotonically. The condition transitions from true to false exactly once. That's your invariant.

Most DSA problems follow the same template: simulate the process with a given candidate and check if it meets constraints. The simulation is the hard part. The binary search is the easy part. Don't confuse the two.

// io.thecodeforge — dsa tutorial

public class IntegerSquareRootBinarySearch {
    // Feasibility: is n² < X?
    private static boolean isFeasible(int n, int x) {
        return (long) n * n < x;
    }

    public static int findMaxN(int x) {
        int left = 0;
        int right = x - 1;  // search space: [0, X-1]
        int answer = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isFeasible(mid, x)) {
                answer = mid;       // mid works, try larger
                left = mid + 1;
            } else {
                right = mid - 1;    // mid fails, go smaller
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        int x = 101;
        int result = findMaxN(x);
        System.out.println("Max n for X=" + x + " is: " + result);
    }
}

Recognizing the Pattern — Keywords That Scream 'Binary Search on Answer'

Competitors list keywords like "minimize the maximum" and "allocate tasks with constraints." Those are useful, but they miss the meta-pattern. Here's how you spot it in the wild.

The question asks for a single number — a rate, a capacity, a distance, a time. The brute force is checking every integer from 1 to some max, and the answer space is monotonic. That's it. Three conditions.

Notice the pattern: the question translates to a threshold where the behavior flips from feasible to infeasible (or vice versa). That's your binary search invariant.

If you hear "allocate," "distribute," "minimize maximum," "maximize minimum," "feasible to complete," or "within budget" — stop. Don't reach for DP or greedy first. Ask: can I binary search on the answer?

9 times out of 10, the answer is yes. And that 10th time, you'll still learn something about the problem structure by trying.

// io.thecodeforge — dsa tutorial

public class KeywordsChecklist {
    // Quick mental checklist before coding any optimization problem:
    // 1. Does the problem ask for a single numeric answer?
    // 2. Is the answer space bounded and integer?
    // 3. Is there a monotonic feasibility function?
    //    i.e., if mid works, do all larger/smaller values also work?
    //
    // If yes, you have a binary search on answer candidate.
    public static void main(String[] args) {
        String[] keywords = {
            "minimize the maximum",
            "maximize the minimum",
            "smallest speed to finish",
            "largest value that satisfies",
            "allocate tasks with constraints",
            "feasible to complete within"
        };
        System.out.println("Keywords that trigger binary search on answer:");
        for (String keyword : keywords) {
            System.out.println("  - " + keyword);
        }
    }
}

Why Iterating Over Every Possible Answer Is Suicide (And What to Do Instead)

When you spot a problem that screams "find the minimum X such that Y holds," your first instinct might be to brute-force every possible value. That's fine for a prototype. In production, that approach dies on anything above trivial input sizes.

The brute-force approach runs in O(N * range) time. If your search space is 10^9 and your feasibility check is O(N), you're looking at 10^9 operations. That's not a solution. That's a timeout.

Binary search on answer cuts that to O(N * log range). For the same 10^9 range, that's about 30 feasibility checks. Thirty. Not a billion. The math is simple: log₂(10^9) ≈ 30. You're literally trading 30 million checks for 30. That's the difference between a five-millisecond response and a five-minute hang.

The senior move: never iterate over the answer space. Always binary search it. Your feasibility function is the only place you spend real time. Make it cheap, make it correct, and let binary search do the heavy lifting.

// io.thecodeforge — dsa tutorial

// Brute force: iterate every possible answer
int bruteForceMinTime(int[] tasks, int workers) {
    int max = 1_000_000_000;
    for (int t = 1; t <= max; t++) {
        if (canComplete(tasks, workers, t)) {
            return t;
        }
    }
    return -1; // runs 1 billion times
}

// Binary search: log(range) checks
int binarySearchMinTime(int[] tasks, int workers) {
    int lo = 1, hi = 1_000_000_000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canComplete(tasks, workers, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo; // runs ~30 times
}

// Shared feasibility check (real cost)
boolean canComplete(int[] tasks, int w, int limit) {
    int needed = 1, load = 0;
    for (int t : tasks) {
        if (load + t > limit) {
            needed++;
            load = 0;
        }
        load += t;
    }
    return needed <= w;
}

The isFeasible() Function Is Where Your Algorithm Lives or Dies

Binary search on answer is a shell game. The search itself is three lines of boilerplate. The real engineering lives in one function: isFeasible(). If that function is wrong, your binary search is just fast garbage.

Here's the trap: isFeasible() must be monotonic. If it returns true for some value X, it must return true for all values greater than X. If your function breaks monotonicity, binary search silently gives you a wrong answer. No crash. No warning. Just subtle bugs in production.

The pattern is always the same: given a candidate answer, can you satisfy the constraints? For Koko, it's "can she eat all bananas in H hours with speed K?" For ship capacity, it's "can all packages ship in D days with capacity C?" For split array, it's "can we split into at most M subarrays with max sum S?"

Your job: write isFeasible() as a standalone unit testable method. Keep it under five lines if possible. If it's longer, you're doing too much. Test it in isolation with edge cases — min values, max values, and exactly at the boundary. That function is the only code that touches the real problem. Get it right, and the binary search is free.

// io.thecodeforge — dsa tutorial

// The entire algorithm depends on this function
boolean isFeasible(int[] piles, int h, double speed) {
    int hoursUsed = 0;
    for (int pile : piles) {
        hoursUsed += (int) Math.ceil(pile / speed);
        if (hoursUsed > h) return false; // early exit
    }
    return true;
}

// Driver: binary search calls this ~30 times
int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 1_000_000_000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isFeasible(piles, h, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

// Test it in isolation
// isFeasible([3,6,7,11], 8, 4.0) → true  (ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8)
// isFeasible([3,6,7,11], 8, 3.0) → false (ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4 = 10 > 8)