Binary Search on the Answer in C++: Five Problems With Nothing to Search

Posted on by NY Comdori

Nobody stores an array of eating speeds. There is no sorted list of ship capacities. And yet both problems are binary search, and recognising that is the single highest-leverage thing in this whole series — because once you see it, a large family of “find the minimum X such that Y” problems stops being a family and becomes one template.

This is the third of three posts on Joseph Choi’s binary search session deck. Part one covered the ten problems where a sorted array supplies the predicate; part two removed the sorting and replaced it with local comparisons and reference points. This post removes the array.

Five problems, all compiled with -Wall -Wextra -fsanitize=undefined,address and differentially tested against brute force before the prose was written. The two overflow traps in the closing section were traced through the actual loops rather than guessed at.

The shift: the search space is the answer

These five problems are the ones that change how people think about binary search, so it is worth stating the shift plainly before the code.

In the first two posts the search space was the input. Here the search space is the set of possible answers, and the input is only how you evaluate the predicate. Nobody stores an array of eating speeds. You binary search over 1…max anyway.

The recipe: name the answer, find a range that certainly brackets it, write a feasibility test, and check that the test is monotone in the answer. If a speed of 7 works then 8 works, so it is. That is the whole method, and it turns a large family of “find the minimum X such that Y” problems into template A.

The recipe

Four steps, in this order. The order matters, because getting step four wrong is how you end up with a loop that terminates and lies.

  1. Name the answer. Not the output of the problem — the quantity you are searching over. For Koko it is the eating speed, not the number of hours. For ship packages it is the capacity, not the number of days. If you cannot name it in one noun, you are not ready to write the loop.
  2. Bracket it. Find a low value that is certainly small enough and a high value that is certainly large enough. Loose is fine — a factor of two costs one iteration — but each bound needs a one-sentence justification, and one of the five problems below is wrong if you get the low bound casually right instead of actually right.
  3. Write the feasibility test. A function that takes a candidate answer and returns yes or no, using the input. This is where all the problem-specific work lives, and it is usually a greedy sweep.
  4. Prove the test is monotone in the candidate. If speed 7 works, does 8? If capacity 15 works, does 16? Say it out loud. Nothing in the code checks this, and when it is false the search returns a plausible wrong number with no crash and no warning.

Then it is template A from part one: while (lo <= hi), pull mid with lo + (hi - lo) / 2, move hi when the candidate is feasible and lo when it is not. The loop exits with lo == hi + 1, so lo is the smallest feasible answer and hi is the largest infeasible one. Every return statement below is one of those two.

The cost changes shape too. An array search is O(log n) in the size of the input. Search on the answer is O(log R × C), where R is the width of the bracketed range and C is the cost of one feasibility test. For Koko that is about 30 probes times a linear sweep — and the log factor is on the range of answers, not on the amount of data.

The first three problems below have feasibility tests that are pure arithmetic, so they are the gentle introduction. The last two have greedy sweeps, which is the shape almost every real instance of this pattern takes.

sqrt(x) (LC 69, Easy)

The deck’s note — numeric value binary search instead of elements — is the transition to this whole section.

int mySqrt(int x) {
    int start = 0, end = x;                       // no special case needed for 0 and 1
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if ((long long)mid * mid > x) end = mid - 1;   // predicate: "mid is too big"
        else start = mid + 1;
    }
    return end;                                   // last false = largest mid with mid*mid <= x
}

The predicate is “mid is too big,” true from floor(sqrt(x)) + 1 onward. The answer is the last false, so return end. No separate equality case is needed, which is why this version has two branches where the deck has three.

The cast is mandatory and it is the whole trap in this problem. mid reaches about 230 for large x, and mid * mid in int arithmetic is undefined behaviour long before that — the deck writes (long long)mid * mid and so should you. The alternative is to compare mid against x / mid, which stays in int at the cost of a division.

I dropped the deck’s if (x < 2) return x; guard and its end = x / 2 upper bound. The guard is unnecessary once the loop starts at start = 0: for x = 0 the first probe already answers it. The x / 2 bound is a genuinely nice tightening — floor(sqrt(x)) ≤ x/2 for every x ≥ 4 — but it buys exactly one iteration out of about 31 and it is what forced the guard in the first place. I verified the version above against sqrtl for every x from 0 to 5,000 and at the boundary values around 231, including 46340² and 2147395600, the largest perfect square below INT_MAX.

Valid Perfect Square (LC 367, Easy)

Same search, different question, so this one keeps the equality branch — you are being asked whether the boundary lands exactly on an integer.

bool isPerfectSquare(int num) {
    int start = 0, end = num;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        long long sq = (long long)mid * mid;
        if (sq == num) return true;
        if (sq < num) start = mid + 1; else end = mid - 1;
    }
    return false;
}

The deck opens with if (num < 2) return num;, which returns an int where a bool is expected. For num = 1 that converts to true and is right. For num = 0 it converts to false, and 0 is a perfect square. LC 367 constrains num ≥ 1, so the case never arises and the submission passes — but the implicit conversion is the kind of thing that outlives the problem it was written for. Deleting the guard fixes it: the loop handles 0 and 1 correctly on its own.

Arranging Coins (LC 441, Easy)

Build a staircase where row i holds i coins; how many rows come out complete? The deck names it immediately: this is a triangle sum, 1 + 2 + 3 + …, and you want the largest level that still fits.

int arrangeCoins(int n) {
    int start = 0, end = n;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        long long used = (long long)mid * (mid + 1LL) / 2;   // 1LL, so mid + 1 cannot overflow an int
        if (used > n) end = mid - 1;
        else start = mid + 1;
    }
    return end;                                   // last complete row
}

The predicate uses the closed form mid(mid+1)/2 rather than adding anything up, so each probe is O(1) and the whole thing is O(log n).

The 1LL matters more than it looks (see also the type traps). In the deck’s (long long)mid * (mid + 1) / 2, the cast binds to mid alone — mid + 1 is still computed in int arithmetic, so if mid ever reached INT_MAX it would overflow before the multiplication ever saw a long long. It never does: I traced the loop for n = INT_MAX and the largest mid it ever evaluates is 1,073,741,823, because the very first probe already overshoots and pulls end down. So the deck’s line is safe, and it is safe by accident rather than by construction. Writing mid + 1LL makes it safe on purpose.

Koko Eating Bananas (LC 875, Medium)

The deck asks the right two questions on its slide: what are we optimising, and what range does it live in? The answer being k, the eating speed, and 1 to max(piles).

long long hoursNeeded(const vector<int>& piles, int speed) {
    long long hours = 0;
    for (int pile : piles) hours += (pile + speed - 1) / speed;   // ceiling division
    return hours;
}
int minEatingSpeed(vector<int>& piles, int h) {
    int start = 1, end = *max_element(piles.begin(), piles.end());
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (hoursNeeded(piles, mid) <= h) end = mid - 1;   // feasible; try slower
        else start = mid + 1;
    }
    return start;                                 // first feasible speed
}

Both bounds deserve a sentence. Speed 1 is always meaningful, so the low end needs no thought. The high end is max(piles) because at that speed every pile takes exactly one hour, giving piles.size() hours total — and the problem guarantees h ≥ piles.size(), so that speed is always feasible and the answer never needs to be larger. Going higher would only waste iterations.

The ceiling division (pile + speed - 1) / speed replaces the deck’s pile / speed + (pile % speed > 0 ? 1 : 0). Same result, one operation instead of three, and it is the idiom worth having in your fingers — it comes up constantly in these problems. It is safe here because pile + speed stays well inside int at these constraints.

The accumulator must be 64-bit: 104 piles of 109 bananas at speed 1 is 1013 hours. The deck writes long, which is 64-bit on Linux and macOS and therefore correct on LeetCode, but only 32 bits under MSVC. long long is 64-bit everywhere, so it is the version that stays correct when the code leaves the judge.

Capacity To Ship Packages Within D Days (LC 1011, Medium)

The deck says this is very similar to Koko with one difference — the capacity has to be at least the maximum weight — and then asks “Why?” It is the best question in the deck, so here is the answer with a number attached.

int daysNeeded(const vector<int>& weights, int capacity) {
    int days = 1, load = 0;
    for (int weight : weights) {
        if (load + weight > capacity) { ++days; load = 0; }
        load += weight;
    }
    return days;
}
int shipWithinDays(vector<int>& weights, int days) {
    int start = *max_element(weights.begin(), weights.end());   // no ship smaller than the heaviest box
    int end = accumulate(weights.begin(), weights.end(), 0);    // one single day
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (daysNeeded(weights, mid) <= days) end = mid - 1;
        else start = mid + 1;
    }
    return start;
}

The greedy daysNeeded loads boxes in order and starts a new day when the next one will not fit. If the capacity is smaller than some box, that box never fits in any day — but the loop happily starts a fresh day and then loads it anyway, overflowing the ship. The count it returns is the number of days for a voyage that physically cannot happen, so the feasibility test is answering a different question from the one its name implies.

Concretely: on weights = [3,2,7,4] with 3 days, a search starting from capacity 1 returns 5, and the correct answer is 7 — a capacity-5 ship cannot carry the weight-7 box at all. Across 100,000 random cases, starting from max(weights) failed zero times and starting from 1 failed 96,161 times. The low bound is not an optimisation. It is what makes the predicate mean what it says.

The upper bound is the sum of all weights: one enormous ship, one day. Between those two, “can it be done in days days?” is monotone in capacity, and template A does the rest.

The five problems on one page

ProblemThe answer being searchedBracketFeasibility testReturns
69 sqrt(x)an integer root0…xmid*mid > xend, last feasible
367 Perfect Squarean exact integer root0…nummid*mid vs numtrue on an exact hit
441 Arranging Coinsa staircase level0…nmid(mid+1)/2 > nend, last complete row
875 Kokoeating speed1…max(piles)hours at that speed ≤ hstart, first feasible
1011 Ship Packagesship capacitymax(w)…sum(w)days at that capacity ≤ dstart, first feasible

Note that the bracket column is where these problems actually differ from one another, and it is also the column with the only genuine trap in the set — see LC 1011 above, and the counterexample in the next section.

Misfits, edge cases, and the things that bite

Search on the answer moves the failure modes around. Index arithmetic stops mattering — there are no indices — and arithmetic width, bound justification, and monotonicity take over.

A feasibility test that answers the wrong question

This is the one to internalise from this post, because it is subtle and it is silent.

LC 1011’s greedy daysNeeded loads boxes in order and starts a new day when the next one will not fit. Hand it a capacity smaller than some box and it starts a fresh day and then loads the box anyway, overflowing the ship. It returns a day count for a voyage that cannot physically happen. The function is not buggy in isolation — it is being asked a question it was never written to answer.

Concretely: on weights = [3,2,7,4] with 3 days, a search starting from capacity 1 returns 5, and the correct answer is 7, because a capacity-5 ship cannot carry the weight-7 box at all. Across 100,000 random cases, starting from max(weights) failed zero times and starting from 1 failed 96,161 times. The low bound is not an optimisation — it is what keeps the predicate honest across the whole range the search will explore.

The general form: your feasibility test must be meaningful, not merely computable, at every candidate in the bracket. When a bound feels arbitrary, ask what your test returns just outside it. Koko passes this check easily — speed 1 is a perfectly sensible speed — which is why the trap only appears in one of the two twins.

Two type traps worth internalising

long is not 64 bits everywhere. Koko’s hour count reaches 1013, which needs 64 bits. long provides them on Linux and macOS, so the deck’s version is correct on LeetCode, and provides only 32 under MSVC. long long is 64-bit on every platform C++ targets.

A cast binds tighter than you want. In (long long)mid * (mid + 1) / 2, the subexpression mid + 1 is still int arithmetic. Here it survives because the loop can never push mid past 230 — I traced it — but the habit to build is to widen the operand that can overflow, not the one next to it: mid + 1LL.

A third, smaller one from LC 367: return num; where the return type is bool compiles silently and means “return num != 0.” It is right for 1 and wrong for 0.

The predicate still has to be monotone

Part one covers this in detail with a worked example of a non-monotone predicate returning a confident wrong answer, and it applies here more than anywhere, because you are writing the predicate yourself rather than inheriting it from a sort order.

The practical test is step four of the recipe, and the reason it is worth doing explicitly is that plausible-looking objectives fail it. “Minimise the largest subarray sum” is monotone in the candidate maximum. “Minimise the variance between subarray sums” is not — raising the allowance does not monotonically change what is achievable — so that variant is not a binary search problem at all, even though it reads almost identically.

When binary search is the wrong tool

  • The data changes between queries. A sorted array with insertions is not a binary search problem; maintaining sortedness costs O(n) per insert. That is a balanced tree or a skip list.
  • n is small. Below a few dozen elements a linear scan usually wins on wall-clock time — it is branch-predictable and cache-friendly, while binary search jumps around memory. Binary search is about asymptotics and about expensive probes, not about being fast on ten items.
  • The predicate is not monotone and cannot be made so. “Find any local minimum in an arbitrary array” works; “find the global minimum in an arbitrary array” does not, at any cost below O(n).
  • You need every answer, not one. Running a binary search per query is O(q log n); if q is comparable to n, a single sort-and-sweep or a prefix sum is usually simpler and faster.
  • The answer space is continuous and the tolerance is unstated. Binary search on real numbers needs a stopping rule — a fixed iteration count or an epsilon — and “loop until lo == hi” does not terminate on doubles.

Where to go next

Five problems is enough to learn the recipe and not enough to trust it. The deck stops here, but this pattern has one of the longest problem lists on LeetCode, and every one of these is the same four steps with a different feasibility test. Worth doing in roughly this order:

  • 1283. Find the Smallest Divisor Given a Threshold — closest to Koko; the test is one arithmetic sweep.
  • 1482. Minimum Number of Days to Make m Bouquets — the first one where the test is a real scan with state, and where the bracket needs thought.
  • 410. Split Array Largest Sum — the canonical Hard in this family. Same greedy sweep as LC 1011, and the same low-bound trap: the candidate must be at least max(nums).
  • 1870. Minimum Speed to Arrive on Time — Koko with a wrinkle in the last leg, and a good exercise in where the ceiling division goes.
  • 1552. Magnetic Force Between Two Balls — maximise the minimum gap instead of minimising a maximum, so the feasibility test flips direction. Doing one of each cures the habit of memorising which way the branches go.
  • 2064. Minimized Maximum of Products Distributed to Any Store — the arithmetic version of LC 410, useful right after it for contrast.
  • 774. Minimize Max Distance to Gas Station — the answer is a real number, not an integer, which breaks while (lo <= hi) entirely. Save it for last; the last bullet in the section above is about exactly this.

LC 1231, Divide Chocolate, belongs on that list too and is a LeetCode Premium problem, so it needs a paid subscription to view.

How to practise this

  1. Before writing anything, say the four steps out loud: the answer, the bracket, the test, the monotonicity argument. Skipping the fourth is how the silent failures happen.
  2. Write the feasibility test as a separate named function and test it on its own, including at the two ends of your bracket. That is where LC 1011’s trap surfaces.
  3. Work out the largest value any accumulator has to hold before choosing its type. Two of the five problems above sit above 88% of INT_MAX at their worst case.
  4. Do one “minimise the maximum” problem and one “maximise the minimum” problem back to back. The branches invert and the templates do not.
  5. In order: 69 → 441 → 875 → 1011, then the list above. LC 875 is the hinge — it is the first one where nothing in the input resembles the answer.

The rest of this series

Credit and the rest of the series

The problem selection, the ordering, and the framing come from Joseph Choi‘s binary search session deck — including the “numeric value binary search instead of elements” framing that opens this family, the two questions on the Koko slide (what are we optimising, and what range does it live in), and the question about LC 1011’s lower bound that turned out to have a concrete counterexample behind it. The C++ here is my own, rewritten where I preferred different bounds or types, and every listing was compiled and differentially tested before publication.

Other pattern write-ups on this site: