Binary Search on Answer

Binary search doesn’t require an array at all. Any time a problem asks you to minimize the maximum (or maximize the minimum) of something, and “can we achieve X?” gets easier to answer as X grows, you can binary search directly over the space of possible answers — no array indices in sight.

What you’ll learn

• How to recognize the cue: “minimize the maximum” / “maximize the minimum”, with a feasibility check that gets monotonically easier or harder.
• The reusable template: binary search over [lo, hi] guided by a feasible(mid) predicate, instead of arr[mid].
• Three worked shapes of the same pattern: Capacity To Ship Packages Within D Days, Koko Eating Bananas, and Split Array Largest Sum.
• Why it costs $O(n \log(\text{range}))$, and the one design step that makes or breaks it: proving your predicate is actually monotonic.

The cue: minimize the maximum, maximize the minimum

Look for a hidden number line of candidate answers where one side is always “too small/slow/tight” and the other side is always “big/generous enough” — with a clean cutoff in between. That cutoff is your answer, and a feasible(candidate) function tells you which side of it you’re on.

Capacity To Ship Packages Within D Days: a conveyor belt ships weights in order, loading as many consecutive packages as fit under a daily capacity before starting a new day. Find the minimum capacity that ships everything within days days.

As capacity grows, the number of days needed only ever decreases (or stays the same) — never increases. That monotonic relationship is exactly what binary search needs, even though there’s no array of “capacities” to search — just the range of integers from the largest single package up to the sum of everything.

The pattern: binary search over a feasibility predicate

binary_search_on_answer.py

def ship_within_days(weights, days):
    def days_needed(capacity):
        # Greedily pack today's shipment; start a new day when the next
        # package would overflow the current one.
        days_used = 1
        current_load = 0
        for w in weights:
            if current_load + w > capacity:
                days_used += 1
                current_load = 0
            current_load += w
        return days_used
 
    lo, hi = max(weights), sum(weights)   # answer must be in [largest single package, ship it all in one day]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if days_needed(mid) <= days:
            hi = mid          # capacity=mid WORKS -- try a smaller (tighter) capacity
        else:
            lo = mid + 1      # capacity=mid too small -- need more room per day
    return lo
 
 
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(ship_within_days(weights, 5))   # expect 15

The shape never changes: pick bounds you’re certain bracket the answer, write a feasible(mid) check, and narrow with lo < hi exactly like the lower_bound template — except mid is a candidate answer, not an array index.

How it works

sketch Binary search on the answer: narrowing the feasible capacity p5.js Pause Restart

lo and hi bracket a range of shipping capacities, not array indices. Each step checks whether mid ships everything within the day limit, then discards the half that can't be the tightest feasible capacity.

Worked example: Koko Eating Bananas

Same shape, different feasibility check. Koko eats at most speed bananas per pile per hour; find the minimum speed that finishes every pile within h hours.

koko_eating_bananas.py

import math
 
def min_eating_speed(piles, h):
    def hours_needed(speed):
        return sum(math.ceil(pile / speed) for pile in piles)
 
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if hours_needed(mid) <= h:
            hi = mid          # speed=mid is fast enough -- try slower
        else:
            lo = mid + 1      # speed=mid too slow -- need faster
    return lo
 
 
print(min_eating_speed([3, 6, 7, 11], 8))   # expect 4

And Split Array Largest Sum — split nums into m contiguous subarrays, minimizing the largest subarray sum — reuses the exact greedy feasibility check from the shipping problem, just renamed:

split_array_largest_sum.py

def split_array_largest_sum(nums, m):
    def pieces_needed(max_sum):
        pieces = 1
        current_sum = 0
        for x in nums:
            if current_sum + x > max_sum:
                pieces += 1
                current_sum = 0
            current_sum += x
        return pieces
 
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if pieces_needed(mid) <= m:
            hi = mid
        else:
            lo = mid + 1
    return lo
 
 
print(split_array_largest_sum([7, 2, 5, 10, 8], 2))   # expect 18

Three different problem statements, the same eleven lines of binary search scaffolding, and only the feasible/hours_needed/pieces_needed helper changes.

Your predicate MUST be monotonic — prove it before you code

Binary search on the answer only works if feasible(x) is False for every value below some cutoff and True for every value at or above it (or vice versa) — with no flip-flopping. Before writing the binary search loop, convince yourself in words: “as the candidate answer increases, does the feasibility check only ever get easier to satisfy (or only ever get harder), with no exceptions?” If you can’t state that one-directional relationship confidently, binary search will silently return a wrong answer — it’ll converge, just not on the right cutoff.

Dry run

ship_within_days([1..10], days=5) — bounds [10, 55]

lo = max(weights) = 10, hi = sum(weights) = 55.

lo	hi	mid	days_needed(mid)	vs limit 5	Action
10	55	32	2	feasible	hi = 32
10	32	21	3	feasible	hi = 21
10	21	15	5	feasible (exactly)	hi = 15
10	15	12	6	too tight	lo = 13
13	15	14	6	too tight	lo = 15

lo == hi == 15, and brute-forcing every capacity from 10 to 55 confirms 15 is the smallest that ships in 5 days.

Row 3 is the row that must not be mishandled. days_needed(15) is exactly 5, the limit — so 15 is feasible and the predicate is <=, not <. hi = mid keeps 15 in the window as a live candidate. Write hi = mid - 1 here and the loop converges on 16: a feasible answer, but not the minimum, and nothing crashes.

Rows 4 and 5 both report 6 days, for capacities 12 and 14. The predicate is not strictly decreasing — it plateaus:

Capacity	10	11	12	13	14	15	16	17	18	19
Days needed	7	6	6	6	6	5	5	4	4	4

Monotonic non-increasing is all binary search requires; strictly decreasing is not needed. The plateau is why the answer is a cutoff rather than a point where the value equals the limit — and why binary search finds it in 5 probes instead of scanning 46 candidates.

min_eating_speed([3, 6, 7, 11], h=8) — bounds [1, 11]

lo	hi	mid	hours_needed(mid)	vs 8	Action
1	11	6	6	feasible	hi = 6
1	6	3	10	too slow	lo = 4
4	6	5	8	feasible	hi = 5
4	5	4	8	feasible	hi = 4

Answer 4, matching brute force. The full picture:

Speed	1	2	3	4	5	6
Hours	27	15	10	8	8	6

Speeds 4 and 5 both take 8 hours — another plateau, and the answer is the left edge of it. Rows 3 and 4 walk down that plateau one step at a time rather than stopping at the first feasible value found. This is the difference between “find a feasible answer” and “find the smallest feasible answer”, and it is entirely encoded in hi = mid plus while lo < hi.

split_array_largest_sum([7, 2, 5, 10, 8], m=2) — bounds [10, 32]

lo	hi	mid	pieces_needed(mid)	vs 2	Action
10	32	21	2	feasible	hi = 21
10	21	15	3	too small	lo = 16
16	21	18	2	feasible	hi = 18
16	18	17	3	too small	lo = 18

Answer 18, realised by the split [7, 2, 5] | [10, 8] — sums 14 and 18, so the largest is 18. Note the greedy pieces_needed never had to find that split. It only counted how many pieces a given ceiling forces; the binary search did the optimising.

Compare the three traces: the loop is byte-for-byte identical across all three problems. Only the helper and the bounds change. That is the point of the pattern — once you recognise it, the scaffolding is free and all the thinking goes into the predicate.

Why lo = max(weights) and not lo = 1

Starting at lo = 1 on the shipping problem still returns 15. So the tighter bound is not what makes the answer correct here — and it is worth knowing why it matters anyway.

days_needed(5) returns 9. But a capacity of 5 cannot ship a package weighing 10 at all: the greedy sees current_load + 10 > 5, opens a new day, sets current_load = 0, then adds 10 — loading a 10-unit package onto a 5-unit belt. The predicate is lying for every candidate below max(weights).

It happens to be a conservative lie — it reports more days than are possible, so those candidates are rejected and the answer survives. Relying on that is fragile: a variant whose predicate saturates instead of inflating (returning a feasible-looking count for an impossible capacity) would converge on nonsense. Pick bounds where the predicate is meaningful, not merely bounds that happen not to break it.

Time and space complexity

Operation	Complexity
Feasibility check (one pass over the input)	$O(n)$
Binary search over the answer range	$O(\log(\text{range}))$ iterations
Total	$O(n \log(\text{range}))$
Space	$O(1)$ extra

range is hi - lo in your chosen bounds — for Koko it’s max(piles), for shipping/splitting it’s sum(nums) - max(nums).

When to use it

• The problem asks to minimize a maximum or maximize a minimum (capacity, speed, largest chunk, smallest gap) subject to a constraint.
• You can write a feasible(candidate) check, typically a single greedy $O(n)$ pass, and you can argue it’s monotonic in candidate.
• The “search space” of candidate answers is large enough that trying every value would be too slow, but bounded enough to pick honest lo/hi.
• Classic tell for “maximize the minimum spacing” variants (aggressive cows / minimize max distance between chosen points): the predicate becomes “can we place everything with at least this much spacing?”, and larger spacing only ever gets harder to satisfy.

The variant map

Variant	The predicate	Canonical problem
Minimise the maximum load	“Does capacity x finish within the day limit?”	1011 Capacity To Ship Packages
Minimise the maximum piece sum	“Does ceiling x need at most m pieces?”	410 Split Array Largest Sum
Minimise a rate	“Does speed x finish within h hours?”	875 Koko Eating Bananas · 1482
Maximise the minimum spacing	“Can I place k items all at least x apart?” — larger x gets harder, so the comparison flips	1552 Magnetic Force · 2max-distance (aggressive cows)
Maximise the minimum share	“Can everyone get at least x?”	1231 Divide Chocolate
kth smallest in a sorted matrix	“How many entries are $\le x$?” — search over values, not indices	378 · 668 · 719
Median of two sorted arrays	Binary search the split point rather than the value	4
Minimise time with parallel workers	“Can x minutes finish all jobs?”	1011 · 2064 · 2560
Real-valued answer	Loop a fixed ~100 iterations, or until hi - lo < eps, instead of lo < hi	644 Maximum Average Subarray II
Smallest divisor / threshold	“Is the summed quotient at most the threshold?”	1283 Find the Smallest Divisor

When the predicate runs the other way

“Maximise the minimum” flips the comparison, and getting it backwards is the most common implementation error in this family. For “place k items at least x apart”, larger x is harder, so:

• feasible(mid) true means “mid works, and maybe more does” -> lo = mid, and mid must be computed as lo + (hi - lo + 1) // 2 (a ceiling midpoint) or the loop hangs when hi == lo + 1.
• feasible(mid) false -> hi = mid - 1.

The floor-versus-ceiling midpoint is not decoration: with lo = mid and a floor midpoint, a two-element window recomputes the same mid forever. If you would rather not carry two templates, negate the objective and keep the minimising one — it is the same trick as using a max-heap by negating values.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 875 — Koko Eating Bananas · Medium

Problem. Koko eats at a speed of k bananas per hour, taking a whole hour per pile even if the pile has fewer than k left. Return the minimum k that lets her finish all piles within h hours.

Constraints. 1 <= len(piles) <= 10^4, piles.length <= h <= 10^9, 1 <= piles[i] <= 10^9.

Examples. piles = [3,6,7,11], h = 8 gives 4 · piles = [30,11,23,4,20], h = 5 gives 30 · h = 6 gives 23

pch.exerciseTag pch.exerciseTitle

Editorial

The array is not what you search. The answer space is, and the enabling property is that feasibility is monotone: if speed k finishes in time, every speed above k does too. That turns “find the minimum feasible” into a boundary binary search.

Time $O(n \log(\max(\text{piles})))$. Space $O(1)$.

Three details:

• hi = max(piles). No speed above the largest pile helps, since each pile already takes exactly one hour at that speed.
• Ceiling division. (p + k - 1) // k keeps everything in integers. math.ceil(p / k) goes through a float and can misround for values near $10^9$.
• The boundary shape (while lo < hi, hi = mid) is required, because mid may itself be the answer. The exact-search shape would skip it.

([1000000000], 2) giving 500000000 confirms the arithmetic scales — a linear scan over speeds would be $10^9$ iterations.

Follow-ups: “How do you know the range?” — 1 is the slowest meaningful speed and max(piles) the fastest useful one. “Prove monotonicity” — more speed never needs more hours; this justifies the search. “Ship packages in D days (LC 1011)?” — the identical shape with a different feasibility function. “What if piles could be consumed partially across hours?” — the ceiling disappears and it becomes plain division.

LC 1011 — Capacity To Ship Packages Within D Days · Medium

Problem. Packages must be shipped in order within days days. Return the minimum ship capacity that makes this possible.

Constraints. 1 <= days <= len(weights) <= 5 * 10^4, 1 <= weights[i] <= 500.

Examples. weights = [1,2,3,4,5,6,7,8,9,10], days = 5 gives 15 · weights = [3,2,2,4,1,4], days = 3 gives 6 · weights = [1,2,3,1,1], days = 4 gives 3

pch.exerciseTag pch.exerciseTitle

Editorial

Structurally identical to LC 875: binary search a candidate answer, with a greedy feasibility check.

Time $O(n \log(\sum \text{weights}))$. Space $O(1)$.

The bounds carry real meaning here:

• lo = max(weights). A capacity below the heaviest package makes shipping impossible at any number of days, so the greedy check would loop forever. Starting at max guarantees every candidate is at least achievable.
• hi = sum(weights). One day is always enough at that capacity, so the answer cannot exceed it.

The greedy day-packing is optimal because the order is fixed: with no freedom to reorder, filling each day as much as possible can never require more days than any other valid packing.

([1,2,3,1,1], 4) giving 3 is worth tracing: capacity 3 packs as [1,2] [3] [1,1] — three days, within the budget of four.

Follow-ups: “Why is greedy packing optimal?” — the fixed-order argument above. “Split an array into k parts minimising the largest sum (LC 410)?” — the same problem restated. “What if packages could be reordered?” — it becomes bin packing, which is NP-hard.

LC 410 — Split Array Largest Sum · Hard

Problem. Split nums into k non-empty contiguous subarrays, minimising the largest subarray sum. Return that minimum.

Constraints. 1 <= len(nums) <= 1000, 0 <= nums[i] <= 10^6, 1 <= k <= min(50, len(nums)).

Examples. nums = [7,2,5,10,8], k = 2 gives 18 · nums = [1,2,3,4,5], k = 2 gives 9 · nums = [1,4,4], k = 3 gives 4

pch.exerciseTag pch.exerciseTitle

Editorial

This is the same problem as LC 1011 with different nouns: “capacity” becomes “the largest allowed subarray sum”, and “days” becomes “parts”. The code is character-for-character the same greedy-plus-binary-search.

Time $O(n \log(\sum \text{nums}))$. Space $O(1)$.

[7,2,5,10,8] with k = 2 gives 18: the split is [7,2,5] and [10,8], sums 14 and 18. No split of this array into two parts does better.

Recognising the equivalence is the point. Once you see “minimise the maximum, over contiguous groups”, the template applies regardless of the story wrapped around it.

There is also a genuine DP solution — dp[i][j] = the best split of the first i elements into j parts — at $O(n^2 k)$. It is worth naming, because it is what you would reach for if the answer space were not monotone. Binary search on the answer is better because feasibility here is monotone.

Follow-ups: “How is this the same as LC 1011?” — the mapping above; the most likely question. “Do it with DP?” — $O(n^2 k)$; mention it as the general fallback. “What if the subarrays need not be contiguous?” — much harder, and the greedy check collapses. “Maximise the minimum instead?” — mirror the comparison, as in Sweep Line-adjacent allocation problems.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

6 problems

1 easy3 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○69Sqrt(x)easyLeetCode Top Interview 150
• ○875Koko Eating BananasmediumBinary search on the minimum feasible eating speedNeetCode 150googleamazonbytedance
• ○1011Capacity To Ship Packages Within D DaysmediumBinary search on the minimum feasible daily capacity
• ○1631Path With Minimum Effortmedium
• ○410Split Array Largest SumhardBinary search on the minimum feasible "largest subarray sum", using the identical greedy-count predicate
• ○774Minimize Max Distance to Gas StationpremiumhardStyle spacing problems -- binary search on the maximum spacing such that everything still fits, with a "can I place all of them with at least this much room?" feasibility check

Interview follow-ups

They ask	What they’re checking	The answer
“Why is binary search valid here? There is no sorted array”	Whether you know the actual precondition	Sortedness is not the requirement — a monotonic predicate is. feasible(x) must be false below a cutoff and true at and above it, with no flip-flopping. The candidate answers form the sorted axis, not the input
“Prove your predicate is monotonic”	Whether you checked or assumed	State the direction in words: “increasing the capacity can only reduce the number of days needed, because every packing valid at capacity c is still valid at c + 1.” A one-line argument like that is what makes the search sound
“What is the complexity? Be careful”	Whether you name the right variable	$O(n \log R)$ where R is the size of the value range, not n. For Koko that is max(piles); for shipping, sum - max. Quoting $O(n \log n)$ is the standard slip
“How do you pick lo and hi?”	Rigour about bounds	Pick values you can prove bracket the answer, and where the predicate is meaningful. For shipping, lo = max(weights) because no smaller capacity can ship the heaviest package — and below that the greedy silently returns a number for an impossible packing
“Your answer is off by one”	The lo < hi / hi = mid discipline	For a minimum, hi = mid on feasible (never mid - 1, since mid may be the answer) and return lo. days_needed(15) == 5 exactly, so 15 must stay in the window; hi = mid - 1 converges on 16 — feasible, but not minimal
“Now maximise the minimum instead”	Whether you can flip it correctly	The comparison inverts: feasible means lo = mid, and the midpoint must become a ceiling, lo + (hi - lo + 1) // 2, or a two-element window loops forever. Or negate the objective and reuse the minimising template
“The answer is a real number, not an integer”	Termination without integers	Loop a fixed number of iterations — 100 doublings of precision is plenty for any float — or until hi - lo < 1e-9. lo < hi never terminates on floats
“Can the predicate be more expensive than $O(n)$?”	Whether you understand the factorisation	Yes, and the total is just predicate cost x log R. LC 378 uses an $O(n)$ count-per-row predicate inside a value search; LC 4 uses an $O(1)$ predicate and lands at $O(\log(m+n))$ overall
“Could you do it without binary search?”	Baseline awareness	Scan every candidate: $O(nR)$. For Koko with max(piles) up to $10^9$ that is hopeless, which is what the constraint is signalling. Say the baseline, then say why the log matters

Self-check

pch.quizTag pch.quizDefaultTitle

1. What is the actual precondition for binary searching on the answer?

   A The input array must be sorted B `feasible(x)` must be monotonic -- false below some cutoff and true at and above it, with no flip-flopping C The answer range must be smaller than the input size D The feasibility check must run in O(1)
   pch.quizShowAnswer

   B — `feasible(x)` must be monotonic -- false below some cutoff and true at and above it, with no flip-flopping — There is often no sorted array anywhere. The sorted axis is the range of candidate *answers*, and monotonicity of the predicate is what lets you discard half of it. If you cannot state the one-directional relationship in words, the search will still converge -- just on the wrong cutoff, silently.

2. For ship_within_days([1..10], days=5), `days_needed(15)` is exactly 5 -- the limit. What must the code do?

   A Treat 15 as infeasible, since it uses the entire budget B Treat 15 as feasible and set `hi = mid`, keeping 15 in the window as a candidate C Return 15 immediately D Set `hi = mid - 1`, since a smaller capacity may also work
   pch.quizShowAnswer

   B — Treat 15 as feasible and set `hi = mid`, keeping 15 in the window as a candidate — The predicate is `<=`, so hitting the limit exactly is feasible. `hi = mid` keeps 15 live and the loop converges on it. `hi = mid - 1` would exclude the answer and converge on 16 -- still a feasible capacity, just not the minimum, with no error raised. That mismatch between `while lo < hi` and `hi = mid - 1` is the most common bug in this template.

3. For the shipping problem, capacities 11, 12, 13 and 14 all need 6 days. Does that plateau break the binary search?

   A Yes -- the predicate must be strictly decreasing B No -- monotonic non-increasing is sufficient, and the answer is the cutoff rather than a point where the value equals the limit C Yes, unless you deduplicate the plateau first D Only if the plateau spans the midpoint
   pch.quizShowAnswer

   B — No -- monotonic non-increasing is sufficient, and the answer is the cutoff rather than a point where the value equals the limit — Days needed goes 7, 6, 6, 6, 6, 5, 5, 4, 4, 4 for capacities 10 through 19 -- flat in places and never rising. Binary search only needs to know which side of the cutoff a probe is on, which a non-increasing function answers fine. The plateau is exactly why the answer is a boundary: 15 is the first capacity that reaches 5 days, found in 5 probes rather than 46.

4. Koko: speeds 4 and 5 both take 8 hours, and h = 8. The trace probes 5, finds it feasible, then probes 4 and also finds it feasible. Why not stop at 5?

   A It should stop -- probing 4 is wasted work B The task is the *smallest* feasible speed, so the loop walks down the plateau to its left edge C Because 5 was only feasible by rounding D Because the loop always runs log(range) iterations regardless
   pch.quizShowAnswer

   B — The task is the *smallest* feasible speed, so the loop walks down the plateau to its left edge — "Find a feasible answer" and "find the smallest feasible answer" are different problems, and the difference is entirely `while lo < hi` plus `hi = mid`. Stopping at the first feasible probe returns 5, which is feasible and wrong. The loop cannot stop early precisely because a plateau means a feasible probe says nothing about whether smaller values also work.

5. What is the time complexity of this pattern?

   A O(n log n) B O(n log R), where R is the size of the value range being searched C O(log n) D O(n) -- the predicate runs once
   pch.quizShowAnswer

   B — O(n log R), where R is the size of the value range being searched — The log is over *values*, not elements. For Koko that is max(piles), which can be 10^9 while n is 10^4 -- so log R is about 30 and unrelated to log n. Quoting O(n log n) is the standard slip, and it matters whenever the value range and the input size differ sharply. More generally the total is (predicate cost) x log R.

6. Why start the shipping search at `lo = max(weights)` rather than `lo = 1`?

   A Because starting at 1 returns a wrong answer B Because below max(weights) the predicate is meaningless -- the greedy "ships" a package heavier than the capacity and returns a count for an impossible packing C To reduce the iteration count from 6 to 5 D Because the answer can never be less than the number of weights
   pch.quizShowAnswer

   B — Because below max(weights) the predicate is meaningless -- the greedy "ships" a package heavier than the capacity and returns a count for an impossible packing — Starting at 1 does still return 15 here, so correctness is not the immediate issue. But days_needed(5) returns 9 for an array containing a 10 -- the greedy opens a new day, resets the load, then loads a 10-unit package onto a 5-unit belt. That lie happens to be conservative, so those candidates get rejected anyway. Relying on a lying predicate is fragile: a variant that saturates rather than inflating would converge on nonsense. Pick bounds where the predicate is meaningful.

7. The problem becomes "maximise the minimum spacing between k placed items." What changes in the template?

   A Nothing -- swap the comparison operator in the predicate B Feasible now means `lo = mid`, and the midpoint must become a ceiling, `lo + (hi - lo + 1) // 2`, or a two-element window loops forever C You must switch to `while lo <= hi` and return `hi` D Binary search no longer applies; use a greedy sweep
   pch.quizShowAnswer

   B — Feasible now means `lo = mid`, and the midpoint must become a ceiling, `lo + (hi - lo + 1) // 2`, or a two-element window loops forever — Larger spacing is harder to satisfy, so the monotonicity runs the other way and the feasible half is the upper one. With `lo = mid` and a floor midpoint, `hi == lo + 1` recomputes the same mid forever -- the ceiling midpoint is what guarantees progress. If you would rather carry one template, negate the objective and keep the minimising version.

8. The answer is a real number rather than an integer. How does the loop terminate?

   A `while lo < hi` still works, using float division B Run a fixed number of iterations (~100), or loop until `hi - lo < eps` C Round the bounds to integers first D Binary search cannot handle real-valued answers
   pch.quizShowAnswer

   B — Run a fixed number of iterations (~100), or loop until `hi - lo < eps` — `lo < hi` never becomes false for floats -- there is always a value between them until you hit representational limits, and relying on that is asking for an infinite or near-infinite loop. A fixed 100 iterations halves the interval 100 times, which exhausts double precision comfortably and needs no epsilon tuning. LC 644 is the canonical instance.

Recall card

• Binary search needs a monotonic predicate, not a sorted array. The sorted axis is the range of candidate answers.
• The shape never changes: prove bounds that bracket the answer, write feasible(mid) (usually one greedy $O(n)$ pass), narrow with while lo < hi, return lo. Shipping, Koko and Split Array share the loop byte for byte.
• State the monotonicity out loud before coding. “Any packing valid at capacity c is still valid at c + 1” is the whole proof.
• For a minimum: feasible -> hi = mid. Never mid - 1 — mid may be the answer. Hitting the limit exactly is feasible (<=).
• Plateaus are fine. Non-increasing is enough; the answer is the cutoff, i.e. the left edge of the plateau. So you cannot stop at the first feasible probe.
• Complexity is $O(n \log R)$ over the value range — max(piles) for Koko, sum - max for shipping. Not $O(n \log n)$.
• Pick bounds where the predicate is meaningful, not just bounds that happen not to break. Below max(weights) the shipping greedy returns a count for an impossible packing.
• “Maximise the minimum” flips it: feasible -> lo = mid, and use a ceiling midpoint lo + (hi - lo + 1) // 2 or the loop hangs. Or negate the objective and reuse one template.
• Real-valued answers: loop ~100 fixed iterations, or until hi - lo < eps. lo < hi never terminates on floats.

Recap

• The cue is “minimize the maximum” / “maximize the minimum” with a feasibility check that only gets easier (or only harder) as the candidate answer grows.
• The template is always the same eleven-ish lines: honest lo/hi bounds, while lo < hi, feasible(mid) decides hi = mid or lo = mid + 1.
• Cost is $O(n \log(\text{range}))$ — one $O(n)$ feasibility pass per binary search step.
• The one thing that can silently break this pattern: a feasibility check that isn’t actually monotonic. Prove monotonicity in words before you trust the binary search around it.

Next: Monotonic Stack — maintaining an increasing or decreasing stack to answer “next greater/smaller” questions in a single pass.