Binary Search III — On the Answer

Review boundary and corrected contracts

Use exact integer ceiling (pile+speed−1)//speed instead of float division. The upper bound must be feasible: positive piles require at least one hour per pile; shipping needs positive days, and splitting uses nonnegative values and 1 ≤ k ≤ n.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Recognise 'minimise/maximise a value subject to a monotone feasibility test' as binary search on the answer range: define feasible(x), find its boundary.

Series: LeetCode — From Basics to Production-Ready · Session 15 / 65 · Phase 1 · Core patterns

Prerequisites. L13 (the binary search template) is required — you'll reuse the same first-True updates, but [lo, hi] is now an inclusive answer range with hi known feasible, not an untested array sentinel. L14 is helpful context but not needed.

Watch first

Optional companions from the original list: Koko, binary search on the answer, and shipping capacity. For each, write down the feasible upper bound and why the test is monotone. External video availability is not verified here; the lesson is self-contained.

What this pattern IS

So far binary search located something inside an array. The most powerful use flips it: you binary search the answer itself.

Look at questions like: "what's the slowest eating speed Koko can use and still finish the bananas in H hours?" or "what's the smallest ship capacity that delivers all packages within D days?" or "split the array into m parts minimising the largest part sum." There's no array to search — the answer is a number somewhere in a known range (e.g. speed from 1 to max-pile).

The trick: define a boolean feasibility predicate feasible(x) = "can we achieve the goal if the answer is x?" For these problems the predicate is monotone: if a speed of x works, any faster speed also works; if a capacity of x works, any bigger capacity works. So feasible looks like False, False, ..., False, True, True, ..., True over the answer range — exactly the shape L13's template hunts. Binary search finds the boundary: the smallest x that's feasible.

The naive approach tries every candidate x from low to high, each test costing O(n) — that's O(range · n). Binary searching the range makes it O(n · log(range)).

Turning a dial until it just works

Real: You're tuning a thermostat: too low and the room never warms, and at some threshold it finally does — and stays warm for anything higher. You don't try every degree; you jump to the middle, check warm-or-not, and halve the dial range each time.

while lo < hi: mid = (lo+hi)//2; if feasible(mid): hi = mid else lo = mid + 1  ->  smallest feasible x.

First principles

Question: Why can you binary search a numeric answer range instead of an array?

Premise: The answer is a single number in a bounded range [lo, hi] you can name up front.

Because: For shipping and nonnegative contiguous splitting, max(items) and sum(items) bound the optimum. Koko instead uses [1, max(piles)]; bounds must be derived for the actual resource and feasibility contract.

Premise: Define feasible(x) = 'is the goal achievable when the answer equals x?', returning a boolean.

Because: It reframes 'find the best value' as 'find the boundary of achievability'.

Premise: feasible is MONOTONE: if x works, every x' > x also works (more speed/capacity/budget never hurts).

Because: Relaxing the resource can only make the constraint easier — feasibility, once true, stays true.

Premise: A monotone boolean over an interval is False...False True...True — one boundary.

Because: Monotonicity forbids feasibility flipping back to False after becoming True.

Premise: L13's 'first True' template over [lo, hi] finds that boundary in O(log(range)) predicate calls.

Because: Each call halves the candidate interval. With W = initial hi − initial lo + 1 and an O(n) predicate, search costs O(n log W); including the input scan gives O(n(1 + log W)), even when W = 1.

Conclusion: Whenever you can write a monotone feasible(x) and bound the answer, binary search the answer range for the boundary.

The templates

Template — binary search the answer for the smallest feasible x

def smallest_feasible(lo, hi, feasible):
    """Smallest x in [lo, hi] with feasible(x) True. feasible must be monotone.
    Assumes at least hi is feasible."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid                # mid works -> maybe smaller does too; keep mid
        else:
            lo = mid + 1            # mid too small -> answer is strictly larger
    return lo                       # smallest feasible value

It uses L13's loop updates but a stronger endpoint contract: hi is a real, feasible answer, so returning it does not mean 'absent'. With an all-False predicate this code still returns the initial hi; callers must reject impossible inputs or choose a different API. The entire skill is proving the predicate and its bounds, not merely recognising the loop.

The recipe (memorise the STEPS, not each problem)

# 1. Identify the answer variable and its range [lo, hi].
#    lo = smallest sane value (often max single element or 1)
#    hi = largest sane value (often the sum, or the max pile)
# 2. Write feasible(x): a greedy/simulation check, O(n), returning True/False.
# 3. Confirm monotonicity: bigger x => easier => stays feasible.
# 4. Binary search [lo, hi] with the 'first True' template.

Example feasibility predicate (Koko)

import math
def feasible_koko(piles, h, speed):
    # hours needed at this speed = sum of ceil(pile / speed)
    hours = sum(((p + speed - 1) // speed) for p in piles)
    return hours <= h            # feasible if it fits in the hour budget

Mental model

Name: Search the dial, not the data

Picture: A dial from lo to hi. Turn it and ask a yes/no question: 'does this value work?' The yeses are all bunched at one end (monotone). You binary search for the FIRST yes — the tightest value that still works.

• Name the answer range [lo, hi] explicitly.

• Write feasible(x): an O(n) greedy/simulation returning a boolean.

• Check monotonicity: more resource => never becomes infeasible.

• Run the 'first True' template on the RANGE, not an array.

Trigger: 'minimise the maximum', 'maximise the minimum', 'smallest capacity/speed/budget such that ...', 'split into k parts minimising the largest'.

Memory / mnemonic

Three letters and a sentence: "BFB — Bound, Feasible, Boundary."

• Bound the answer: what's the smallest and largest x could be? Write lo, hi first.
• Feasible(x): an O(n) yes/no check. Say the sentence "if the answer were x, could I hit the goal?" Code it as a greedy pass.
• Boundary: run L13's exact template on the range. "First True is the answer."

The trigger phrase that should fire this pattern instantly: "minimise the maximum" (or maximise the minimum). Whenever you hear it, reach for BFB. The other tell: the answer is a number in a range, not a position in the input.

The trap

Myth: Binary search only applies to a sorted array, so if there's no array to sort, binary search is off the table.

Truth: Binary search applies to any MONOTONE predicate over an ordered domain — including a numeric answer range with no array in sight. The domain is the candidate answers; the 'sortedness' is the monotonicity of feasible(x).

Why: The template only needs a boundary between False and True. A sorted array is just the special case where the predicate is 'value >= target'; feasibility predicates are the general case.

Test: Solve Koko Eating Bananas. There's no target to find in the piles — you binary search the SPEED range 1..max(piles), proving array-search was never the requirement.

What reviewers actually ask

These practice problems vary the feasibility test while keeping the boundary loop; no company-specific frequency claim is needed.

• Koko Eating Bananas (875) · Medium · Practice selection. — probes: do you spot 'minimise the speed subject to a time budget' as a monotone predicate? Follow-up: what are the correct lo/hi bounds?
• Capacity To Ship Packages Within D Days (1011) · Medium · Practice selection. — probes: feasible(capacity) via a greedy day-count simulation; lo = max(weight), hi = sum. Follow-up: why lo can't be smaller than the biggest single package.
• Split Array Largest Sum (410) · Hard · Practice selection. — probes: 'minimise the largest subarray sum over k splits' — the canonical minimise-the-maximum. Follow-up: the DP alternative and why binary search is simpler.
• Minimum Number of Days to Make m Bouquets (1482) · Medium · Practice selection. — probes: feasible(day) with a scan for consecutive bloomed flowers. Follow-up: impossible-case detection (m*k > n).
• Find the Smallest Divisor Given a Threshold (1283) · Medium · Practice selection. — probes: feasible(divisor) via sum of ceilings ≤ threshold. Follow-up: identical structure to Koko — can you see it?
• Sqrt(x) (69) · Easy · Practice selection. — probes: largest m with m*m ≤ x — search-on-answer in its simplest form. Follow-up: extend to real-valued precision.

Universal probe: "there's no array to search — what are you binary searching over, and why is it monotone?" Name the answer range and the monotonicity.

Worked solutions

1. Koko Eating Bananas (875)

Plain words: a nonempty list of positive integer piles and an integer H with H >= len(piles). Each hour Koko eats up to speed bananas from one pile (a partial pile still uses a full hour). Find the minimum positive integer speed to finish within H hours. If H is smaller than the number of piles, no speed works: reject that input rather than interpreting the returned upper bound as a solution.

For positive integers p and speed, write p = q*speed + r, with 0 <= r < speed. The required hours are q plus one exactly when r is nonzero; (p + speed - 1)//speed computes that without a float conversion. For example, (2**53 + 1)/1 can round before math.ceil sees it, whereas the integer formula remains exact.

Brute force: try every speed from 1 upward until one fits — O(max_pile · n). Insight: feasible(speed) = "hours needed ≤ H" is monotone (faster is never worse), so binary search speed in [1, max(piles)].

import math
def minEatingSpeed(piles, h):
    def hours_at(speed):
        return sum(((p + speed - 1) // speed) for p in piles)   # O(n)
    lo, hi = 1, max(piles)          # slowest possible = 1, fastest useful = biggest pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if hours_at(mid) <= h:      # feasible -> maybe even slower works
            hi = mid
        else:
            lo = mid + 1            # too slow -> need faster
    return lo

Complexity: O(n · log(max_pile)) time, O(1) memory. Follow-up — "why hi = max(piles)?": at that speed every pile takes exactly one hour, the fewest possible; going faster never reduces the hour count further.

Goal: Solve Find the Smallest Divisor Given a Threshold (1283): smallest d with sum(ceil(n/d)) <= threshold.

Hint: Same shape as Koko — search d in [1, max(nums)] with the same ceiling sum. Require nonempty positive integers and threshold >= len(nums) so the upper bound is feasible.

import math
def smallestDivisor(nums, threshold):
    def total(d):
        return sum(((x + d - 1) // d) for x in nums)
    lo, hi = 1, max(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if total(mid) <= threshold:
            hi = mid
        else:
            lo = mid + 1
    return lo

2. Capacity To Ship Packages Within D Days (1011)

Plain words: nonempty positive integer package weights must ship in order; each day a ship carries a prefix of the remaining packages up to its capacity. With integer D >= 1, find the least capacity that ships everything within D days.

Why the greedy check is sufficient: at a fixed capacity, greedy takes the longest prefix that fits. No valid first day can end later. Inductively, after any number of days greedy has shipped at least as far as any competing schedule: starting later leaves a suffix of the competitor's next load, which still fits because weights are positive. Thus greedy uses the fewest days. This proof depends on fixed order and nonnegative loads, not on arbitrary bin packing.

Insight: feasible(cap) = greedily pack days and count how many are needed; feasible iff days_needed ≤ D. Monotone (bigger ship never needs more days). Bounds: lo = max(weights) (must fit the heaviest single package in one day), hi = sum(weights) (one giant day).

def shipWithinDays(weights, days):
    def days_needed(cap):
        needed, load = 1, 0
        for w in weights:
            if load + w > cap:      # can't fit -> start a new day
                needed += 1
                load = 0
            load += w
        return needed
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if days_needed(mid) <= days:   # feasible -> try smaller capacity
            hi = mid
        else:
            lo = mid + 1               # infeasible -> need more capacity
    return lo

Complexity: O(n · log(sum)) time, O(1) memory. Follow-up — "why lo = max(weights)?": a capacity below the heaviest package can never load that package on any day, so no capacity smaller than the max is ever feasible.

3. Split Array Largest Sum (410)

Plain words: split a nonempty array of nonnegative integers into exactly k contiguous non-empty subarrays, where 1 <= k <= len(nums), minimising the largest subarray sum.

Why checking at most k parts solves exactly k: if a feasible partition has fewer parts, split any part containing two or more elements. Neither new sum exceeds the old sum because all elements are nonnegative. Repeat until there are k parts. For [7, 2, 5, 10, 8], limit 18 yields [7, 2, 5] | [10, 8]; limit 17 greedily needs three parts, so the optimum for k=2 is 18.

Negative values invalidate both the greedy proof and these bounds. For [5, -4], k=1 has optimum 1, below max(nums)=5; a prefix over a limit might later fall back under it. The displayed function is not a signed-array solver.

Insight: this is the archetypal minimise the maximum. feasible(limit) = "can we split into ≤ k parts if no part may exceed limit?" — greedily start a new part whenever adding the next element would exceed limit, count parts. Monotone (a bigger limit never needs more parts). Bounds: lo = max(nums), hi = sum(nums).

def splitArray(nums, k):
    def parts_needed(limit):
        parts, cur = 1, 0
        for x in nums:
            if cur + x > limit:     # exceeds the cap -> open a new part
                parts += 1
                cur = 0
            cur += x
        return parts
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if parts_needed(mid) <= k:  # feasible within k parts -> try a tighter cap
            hi = mid
        else:
            lo = mid + 1            # needs too many parts -> raise the cap
    return lo

Complexity: O(n(1 + log W)) time, O(1) auxiliary memory, with W = sum(nums) − max(nums) + 1. This also covers an all-zero array. A direct O(k·n²) partition DP compares every last cut and remains useful for richer costs; there is no universal preference independent of constraints.

Tradeoff

Decision: Solve a 'minimise the maximum / smallest feasible value' optimisation.

Name: Linear scan of candidate answers

Gain: Trivial to reason about; obviously correct.

Cost: O(range · n) — times out when the answer range is large.

Pick: Only when the range is tiny (a few dozen candidates).

Name: Binary search on the answer

Gain: O(n · log(range)); short code once feasible(x) is written.

Cost: Requires a MONOTONE feasibility predicate and correct bounds; a wrong lo/hi silently breaks it.

Pick: The default whenever feasible(x) is monotone and the range is bounded.

Name: Dynamic programming

Gain: Models partition costs and richer constraints directly; may also supply a feasibility test when greedy is invalid.

Cost: Often O(k·n^2) or worse; more code; more bug surface.

Pick: When its state captures constraints the greedy check does not, or its cost is preferable for the input bounds. Reconstructing a partition alone does not require DP: after finding the limit, retain greedy cuts and split further to reach k parts.

Verdict: Use binary search here because feasibility is both monotone and cheaply decidable by a proved greedy scan. Monotonicity alone says nothing about the cost of deciding feasibility; compare that cost, the answer range, and the alternatives. DP can be appropriate even when feasibility is monotone.

Where this shows up

A deterministic capacity model can ask for the smallest resource budget meeting a deadline. To use this method, prove that a feasible schedule remains feasible when the budget increases (for example, extra machines may remain idle) and provide a correct feasibility checker. Measured latency in an autoscaler may fluctuate with contention, warm-up and noise; it is not automatically a monotone oracle. These lessons do not establish how any particular production autoscaler or rate limiter operates.

Checkpoint

You can now…

• Recognise 'minimise the maximum / smallest feasible x' as binary-search-on-answer.

• Name a correct answer range [lo, hi] for such problems.

• Write a monotone feasible(x) as an O(n) greedy or simulation.

• Reuse the L13 'first True' template unchanged over a numeric range.

• Justify the bounds (why lo = max element, hi = sum) for packing problems.

• Choose binary-search-on-answer when feasibility is monotone, its checker is correct and affordable, and the resulting cost suits the input bounds.

Quiz

Self-check (answer follows each question).

Recall check

Q: In binary-search-on-answer, what exactly are you binary searching over?

A: The range of candidate answer VALUES (e.g. speeds, capacities, sums), not positions in the input array.

Q: What property must feasible(x) have for the template to work, and what does it mean?

A: Monotonicity: once feasible(x) is True, feasible(x') is True for all x' > x — more resource never makes it infeasible.

Q: For Capacity To Ship Packages, why is lo = max(weights) and not 1?

A: A capacity below the heaviest single package can never load that package on any day, so no smaller capacity is ever feasible.

Q: State the three-step recipe (mnemonic) for these problems.

A: BFB: Bound the answer range, write the Feasible predicate, binary search for the Boundary (first True).

Q: Why is binary-search-on-answer O(n log(range)) rather than O(range · n)?

A: For W candidate integers, halving takes O(log W) predicate calls rather than W. Multiply by the checker cost, here O(n); include the initial O(n) bounds scan, giving O(n(1 + log W)).

Q: ★ Stretch: how would you adapt the template to MAXIMISE a value (e.g. maximise the minimum distance) instead of minimise?

A: For a True...True False...False predicate, require an inclusive range whose lower endpoint is feasible, then search for the LAST True. Concretely, when feasible(mid) is True set lo = mid (keep it, search higher) and when False set hi = mid − 1, using a mid that rounds UP (mid = lo + (hi − lo + 1)//2) to avoid an infinite loop.

Stretch: true

Practice queue

+7d / +21d mark spaced-repetition anchors.

• Sqrt(x) (69) — Easy · simplest search-on-answer.
• Koko Eating Bananas (875) — Medium · the archetype · +7d anchor.
• Find the Smallest Divisor Given a Threshold (1283) — Medium · Koko in disguise.
• Capacity To Ship Packages Within D Days (1011) — Medium · greedy feasibility.
• Minimum Number of Days to Make m Bouquets (1482) — Medium · scan-based predicate.
• Split Array Largest Sum (410) — Hard · minimise the maximum · +21d anchor.
• Minimize Max Distance to Gas Station (774) — Hard · real-valued search-on-answer.

Corrective source notes

• Binary Search - Algorithms for Competitive Programming — Binary search can find a transition in an arbitrary monotone Boolean predicate. Checked 2026-10-07.

• CPython v3.14.0 numeric types — arbitrary-precision integers and floor division; checked 2026-10-09. The ceiling identity and greedy partition proofs above are mathematical derivations, not claims certified by the Python documentation.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.