Binary Search on the Answer: The Pattern Most People Miss

TL;DR: Binary search does not require a sorted array. It requires a question whose answer flips from no to yes exactly once as you move along a range, and never flips back. That property is called monotonicity, and once you see it you can binary search over things that are not arrays at all: eating speeds, ship capacities, days, or lengths. This is the disguise that turns a family of problems that look like hard optimization into fifteen lines of code, and it is the single most common reason a candidate spends thirty minutes on a question that has a five minute solution.

This is the eighth deep dive in our pattern series (the full map lives in the hub), and it is the one the K-way Merge post promised. Modified binary search covers two related skills. The first is handling the classic variants where the array is sorted but the plain textbook search does not quite fit. The second, which is where most candidates lose the question, is recognizing that the thing you should be searching is not the input at all. We will do both, in that order.

The tell: how to recognize a binary search problem

Start with the obvious signals, then the ones that hide.

The array is sorted, but the target is not a plain equality:

• "find the first or last position of a value"
• "find the insertion point"
• "the array is sorted but rotated"
• "find a peak element"

The array is not sorted, or there is no array at all:

• "the minimum speed / capacity / size / days such that something is possible"
• "minimize the maximum" or "maximize the minimum"
• "the smallest divisor / largest sum / least time to finish"
• the answer is a number in a range you can name, and checking a candidate answer is cheap

That second group is the disguise. The words "minimize the maximum" are nearly a guarantee, because that phrasing almost never has a greedy solution and almost always has a monotonic feasibility check.

The one property the whole pattern rests on

Here is the sentence that is the pattern: binary search needs monotonicity, not sortedness.

A sorted array is just one example of monotonicity. What the algorithm actually needs is a yes/no question feasible(x) whose answers, laid out across the range of possible x, look like this:

x:         1     2     3     4     5     6     7     8
feasible:  no    no    no    yes   yes   yes   yes   yes
                             ^
                       the boundary you want

Once the answers are false for a while and then true forever, you can discard half the range on every check, because a single test tells you which side of the boundary you are on. Nothing about that argument mentions an array.

So before writing any code, answer three questions out loud:

1. What is the answer space? The lowest and highest values the answer could possibly take.
2. What is feasible(x)? A cheap check that says whether x is good enough.
3. Why is feasible monotonic? One sentence. If a speed of 5 finishes in time, then 6 certainly does, because eating faster never takes longer.

That third question is what interviewers are grading. Candidates who state it get credit even before they finish coding, and candidates who skip it often apply the pattern to a question where feasibility is not monotonic and get a wrong answer that looks confident.

The template

Use one loop form for every boundary search and stop rewriting it per problem. This version finds the smallest x for which feasible(x) is true:

def smallest_feasible(lo, hi, feasible):
    while lo < hi:                       # strict: stops when the range is one value
        mid = lo + (hi - lo) // 2        # bias low, avoids overflow in Java and C++
        if feasible(mid):
            hi = mid                     # mid might be the answer, so keep it
        else:
            lo = mid + 1                 # mid is too small, discard it
    return lo                            # lo == hi == the boundary

Three details make this loop safe. The condition is lo < hi, not lo <= hi, so it exits with a single candidate rather than needing a separate return. The feasible branch assigns hi = mid rather than mid - 1, because mid itself may be the answer. The infeasible branch assigns lo = mid + 1, which is what guarantees progress and prevents an infinite loop. Change one of those three and the other two stop being correct together.

Now Koko Eating Bananas, which is the canonical form:

def min_eating_speed(piles, h):
    def feasible(speed):
        hours = sum((p + speed - 1) // speed for p in piles)   # ceiling division
        return hours <= h

    lo, hi = 1, max(piles)               # slowest useful speed, fastest useful speed
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

The entire problem-specific work is the four lines of feasible and the two bounds. That is the pattern: you are not designing an algorithm, you are naming a search space and writing a checker.

The classic variants, briefly

The answer-space disguise is the valuable half, but interviewers still ask the sorted-array variants, and they use the same loop.

• First and last position of a value: two boundary searches. The first position is the smallest index where nums[i] >= target, the last is one before the smallest index where nums[i] > target. Both are the template with a different feasible.
• Search in a rotated sorted array: at any midpoint, one of the two halves is guaranteed to be sorted. Work out which one, check whether the target lies inside it, and discard the other half. The discard argument, not the code, is what gets graded.
• Find a peak element: compare nums[mid] with nums[mid+1] and walk uphill. This one surprises people because the array is unsorted, which makes it a good bridge to the answer-space idea.
• Median of two sorted arrays: binary search over the partition point rather than over values. The hardest common member of the family, and the clearest demonstration that the search space is something you choose.

Want the whole family taught in order? The modified binary search chapter of Grokking the Coding Interview builds from boundary searches through rotated arrays and up to answer-space problems like Split Array Largest Sum, with worked traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The escalations interviewers actually reach for

• Koko Eating Bananas: the introduction to the disguise. Speed is the answer space, total hours is the check.
• Capacity To Ship Packages Within D Days: the same shape with one extra constraint. The lower bound is max(weights), not 1, because a package must fit on one ship. Getting the bounds right is the whole difficulty.
• Minimum Number of Days to Make m Bouquets: the answer space is days, and the check is a scan for consecutive bloomed flowers.
• Find the Smallest Divisor Given a Threshold: nearly identical to Koko, useful for confirming you have the template rather than a memorized solution.
• Split Array Largest Sum: the hard version. The answer space is the largest allowed subarray sum, and the check is a greedy count of how many pieces that limit forces. It is also solvable with dynamic programming, and knowing that binary search beats it is worth saying.
• Kth Smallest Element in a Sorted Matrix: binary search over values rather than positions, counting how many entries fall below each candidate.

The three mistakes that sink candidates

1. Mixing loop forms and spinning forever. The classic failure is while lo < hi combined with hi = mid in one branch and lo = mid in the other. When the range narrows to two values, mid equals lo, nothing changes, and the loop never ends. Pick the template above and keep the three details together.

2. Wrong bounds. If hi starts below the true answer, the search returns a confidently wrong value. In Capacity To Ship Packages, starting lo at 1 rather than max(weights) produces a capacity that cannot hold the largest package. Derive both bounds from the problem instead of guessing.

3. Applying the pattern when feasibility is not monotonic. If a larger x can turn a yes back into a no, binary search will land on an arbitrary point. Before coding, say why the property holds. If you cannot, the problem is asking for something else.

Practice ladder

In order, each rung adding one wrinkle.

1. Binary Search (E): the plain form, written with the template above.
2. Search Insert Position (E): your first boundary search.
3. Find First and Last Position (M): two boundaries, one array.
4. Find Peak Element (M): unsorted input, still binary searchable.
5. Search in Rotated Sorted Array (M): rehearse the discard argument.
6. Koko Eating Bananas (M): the first answer-space problem.
7. Capacity To Ship Packages Within D Days (M): bounds discipline.
8. Minimum Number of Days to Make m Bouquets (M): a scan as the checker.
9. Split Array Largest Sum (H): the hard version of the same idea.
10. Stretch: Median of Two Sorted Arrays (H), searching a partition.

Then write the tell in your own words ("I should suspect binary search when ___") and move on. Recognition, not volume, is the skill.

The takeaway

One property (monotonicity, not sortedness), one loop you never rewrite (lo < hi, hi = mid, lo = mid + 1), and three questions to answer before coding (what is the answer space, what is the check, why is the check monotonic). Learn to hear "minimize the maximum" as "binary search the answer" and a whole tier of problems that look like hard optimization becomes routine. The full map of where this sits among the other 41 patterns is in the complete pattern guide. Next in the series: Prefix Sum, where one identity makes every range total O(1).

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79 with lifetime access. Short on time? Grokking 75 includes the essential binary search problems in its 6-week plan.

FAQs

What does "binary search on the answer" mean? Instead of searching for a position inside an array, you search the range of values the answer could take. At each step you test a candidate answer with a feasibility check and discard half the range. It works whenever the check is monotonic, meaning once it starts returning true it never returns false again.

How do I know if binary search applies when the input is not sorted? Ask whether you can write a cheap function that takes a candidate answer and returns yes or no, and whether a larger candidate can ever turn a yes into a no. If it cannot, the answer space is effectively sorted by that check, and binary search applies.

Why does my binary search loop run forever? Almost always a mismatch between the loop condition and the updates. With while lo < hi, one branch must assign hi = mid and the other must assign lo = mid + 1. If both branches can leave the range unchanged when it holds two values, the loop cannot make progress.

Should I use lo <= hi or lo < hi? Use lo < hi for boundary searches, which is most of this family, and return lo at the end. Use lo <= hi only when searching for an exact match that may not exist and you want to return -1. Mixing the two conventions inside one solution is where bugs come from.

Is binary search on the answer actually asked at FAANG companies? Frequently. Koko Eating Bananas and Capacity To Ship Packages are common screens, Split Array Largest Sum appears in Google and Amazon loops, and the phrasing "minimize the maximum" shows up across companies. It is one of the most reliable patterns to recognize by wording alone.