Binary Search on a Monotonic Answer Space

Good to see you again. In the previous lesson, sorting intervals created an order that made a local merge decision safe. Here, the input itself may not be sorted—or even be an array we want to search. Instead, we construct an ordered range of possible answers and ask a yes/no question about each candidate.

This pattern appears frequently in interview problems framed as “minimum capacity,” “minimum speed,” “maximum threshold,” or “earliest time.” By the end of this lesson, you will be able to identify a monotonic answer space, define a correct feasibility predicate, choose sound bounds, and implement a reliable Java binary-search template.

---

1. Binary search is really boundary search

The familiar version of binary search searches a sorted array for a value. Its more general form searches for a boundary in any ordered domain where a Boolean predicate changes only once.

Suppose candidates are integers in a range $[L,R]$. Define:

$$\mathrm{feasible}(x)$$

as a function that says whether candidate $x$ meets the requirement.

For a minimization problem, the ideal shape is:

false, false, false, true, true, true

The answer is the first true candidate.

For example:

• minimum worker count that completes a job before a deadline;
• minimum API rate limit that sustains a required throughput;
• minimum database shard count that keeps storage per shard under a limit;
• minimum ship capacity that delivers packages within a fixed number of days;
• minimum eating speed that finishes all banana piles within a fixed number of hours.

The candidate values are ordered, but they are not necessarily present in the input. That distinction is the central recognition skill.

Do not ask, “Is the input sorted?”
Ask, “Can I order the possible answers, and does feasibility change only once across that order?”

The formal name is a monotonic predicate. For the first-true pattern:

$$x_1<x_2\wedge \mathrm{feasible}(x_1)⟹\mathrm{feasible}(x_2)$$

In words: once a candidate works, every larger candidate also works.

---

2. A repeatable recognition method

When a problem asks for an optimal integer value, use this sequence before writing code.

1. State the objective precisely

Look for language such as:

• “minimum speed/capacity/number of days”
• “smallest value that satisfies”
• “maximum feasible threshold”
• “earliest time at which”
• “largest value under a constraint”

The word minimum alone is not enough. You need a way to test a proposed answer.

2. Define the candidate parameter

Choose one integer parameter, such as:

• capacity $C$,
• speed $k$,
• time $t$,
• maximum allowed distance $d$,
• number of partitions $p$.

3. Write feasible(candidate)

The predicate should return a Boolean answer, not the optimum itself.

For example:

feasible(capacity) = Can all packages be shipped within D days?

or:

feasible(speed) = Can all piles be finished within H hours?

4. Prove the monotonic direction

Do this verbally before coding.

For a minimum capacity problem:

• If capacity $C$ works, any larger capacity works.
• If capacity $C$ fails, any smaller capacity fails.

That creates the false-then-true shape required for first-true binary search.

5. Establish meaningful bounds

Bounds are part of the proof, not arbitrary placeholders.

For a capacity problem where one item cannot be split:

$$\text{low}=\max (\text{item size})$$

A lower capacity cannot even hold the largest individual item.

A common upper bound is:

$$\text{high}=\sum (\text{item size})$$

because that capacity can process all items in one batch or one day, assuming the problem allows it.

6. Choose one binary-search template and preserve its invariant

Many binary-search bugs come from combining lines from two different templates. In this lesson, we will use one clear form:

Find the smallest feasible value, given that the upper bound is feasible.

---

3. Worked example: Koko Eating Bananas

The standard Koko problem gives positive pile sizes and $h$ available hours. Koko chooses an integer speed $k$, measured in bananas per hour, and eats from one pile per hour. We need the smallest speed that finishes every pile within $h$ hours.

For:

piles = [3, 6, 7, 11]
h = 8

the candidate is $k$, Koko’s eating speed.

The number of hours required for a pile with $p$ bananas is:

$$\lceil \frac{p}{k}\rceil$$

So the feasibility predicate is:

$$\mathrm{feasible}(k)=\left(\sum _{p\in \text{piles}}\lceil \frac{p}{k}\rceil \right)\le h$$

The monotonic proof is straightforward:

• At a higher speed, each pile takes the same or fewer hours.
• Therefore, total required hours never increase as $k$ increases.
• If speed $k$ is sufficient, every speed greater than $k$ is also sufficient.

The useful bounds are:

$$\text{low}=1$$ $$\text{high}=\max (\text{piles})$$

At a speed equal to the largest pile, each nonempty pile takes one hour. Thus, high is feasible whenever $h$ is at least the number of piles, which is part of the usual problem contract.

Trace the search

We do not evaluate every speed. Binary search evaluates only enough candidates to isolate the boundary.

Round	Current range	Middle speed	Hours required	Feasible?	Next range
1	[1, 11]	6	6	Yes	[1, 6]
2	[1, 6]	3	10	No	[4, 6]
3	[4, 6]	5	8	Yes	[4, 5]
4	[4, 5]	4	8	Yes	[4, 4]

The final answer is 4.

Notice the nature of the decision:

• A feasible middle value is a valid answer, but perhaps not the minimum answer. Keep searching left, including the middle value.
• An infeasible middle value and every smaller value can be discarded. Search to the right.

---

4. The first-feasible Java template

This inclusive-range template works when:

1. low is a valid lower bound;
2. high is known to be feasible;
3. the predicate is monotonic from false to true.

int left = low;
int right = high;

while (left < right) {
    int mid = left + (right - left) / 2;

    if (feasible(mid)) {
        right = mid;
    } else {
        left = mid + 1;
    }
}

return left;

The crucial invariant is:

The smallest feasible answer is always inside the inclusive range [left, right], and right is feasible.

When mid is feasible, the answer is in [left, mid], so assigning right = mid retains mid as a possible answer.

When mid is infeasible, the answer must be greater than mid, so left = mid + 1 safely removes it.

The loop ends only when left == right, leaving one candidate: the first feasible value.

Why use this midpoint expression?

Use:

int mid = left + (right - left) / 2;

rather than:

int mid = (left + right) / 2;

The latter can overflow if both bounds are large positive integers. It may not matter in a small interview example, but using the safe form should become automatic.

---

5. Production-safe Java solution

The following implementation makes the assumptions explicit:

• piles are positive;
• a valid speed must be positive;
• if h < piles.length, no speed can work because each nonempty pile requires at least one hour;
• the hour total uses long, because sums can exceed the range of int.

public final class KokoBananas {

    private KokoBananas() {
    }

    public static int minEatingSpeed(int[] piles, int h) {
        if (piles == null || piles.length == 0 || h <= 0) {
            throw new IllegalArgumentException("Piles must be nonempty and h must be positive");
        }

        int maxPile = 0;

        for (int pile : piles) {
            if (pile <= 0) {
                throw new IllegalArgumentException("Every pile must be positive");
            }
            maxPile = Math.max(maxPile, pile);
        }

        // At least one hour is required for each nonempty pile.
        if (h < piles.length) {
            return -1;
        }

        int left = 1;
        int right = maxPile;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (canFinishWithinHours(piles, h, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private static boolean canFinishWithinHours(
            int[] piles,
            int maxHours,
            int speed
    ) {
        long hours = 0;

        for (int pile : piles) {
            hours += (pile + (long) speed - 1) / speed;

            // Avoid needless work once the candidate is known to fail.
            if (hours > maxHours) {
                return false;
            }
        }

        return true;
    }
}

The expression below performs integer ceiling division safely:

(pile + (long) speed - 1) / speed

For example, with a pile of 7 and speed 3, ordinary integer division gives 2, which is wrong because two hours cover only six bananas. Ceiling division gives 3.

Complexity

Let:

• $n$ be the number of piles;
• $M$ be the largest pile size.

Each feasibility check scans the piles:

$$O(n)$$

Binary search performs logarithmically many checks over the range from $1$ to $M$:

$$O(\log M)$$

Therefore, total time is:

$$O(n\log M)$$

Extra space is:

$$O(1)$$

excluding the input itself.

---

6. Transfer the pattern: minimum ship capacity

A different prompt can have exactly the same structure.

Given package weights in fixed order and a number of days, find the minimum ship capacity that delivers all packages within the deadline.

For a candidate capacity $C$, canShip(C) greedily loads packages until adding the next package would exceed $C$; it then starts a new day.

The bounds follow from the domain:

Bound	Reason
low = max(weights)	Every package must fit on the ship.
high = sum(weights)	This capacity ships everything in one day.

The monotonic argument is also the same: increasing ship capacity cannot require more shipping days. A capacity that works remains valid at any greater capacity.

This is why the Koko and ship-capacity problems should not be memorized as separate solutions. They are instances of one design pattern:

1. Define an ordered answer parameter.
2. Write a deterministic feasibility check.
3. Prove that feasibility changes only once.
4. Find the boundary with binary search.

---

7. Failure modes to catch in an interview

Searching without proving monotonicity

A check function alone does not justify binary search. Some real systems are not monotonic: increasing concurrency, for example, may improve throughput until contention, rate limiting, or downstream saturation makes it worse.

For interview problems, state the monotonic proof. For production tuning, validate the assumption with measurements rather than treating it as mathematically guaranteed.

Using invalid bounds

For Koko, max(piles) is a useful feasible upper bound. A bound such as sum(piles) is valid but looser and obscures the reasoning. A lower bound such as sum(piles) / h is not necessarily safe because Koko cannot divide one hour across multiple piles.

Mixing templates

This lesson’s template uses:

while (left < right)

and, on feasibility:

right = mid;

Do not combine it with a while (left <= right) loop and right = mid - 1 unless you also adopt that template’s separate answer-tracking invariant.

Treating the predicate as the answer

canFinishWithinHours answers only “does this speed work?” It does not compute the minimum speed. Binary search is responsible for locating the smallest working speed.

Overflow in the check function

Even if pile and speed fit in int, the sum of required hours may not. Use long for aggregates. Also cast before adding speed - 1 to avoid overflow in ceiling division.

---

Interview explanation to rehearse

A concise, strong explanation would be:

“I will binary search the answer rather than the input. Let $k$ be the eating speed and define feasibility as whether the sum of ceiling divisions for all piles is at most $h$. If a speed works, every larger speed works because each pile takes no more hours, so feasibility is monotonic: false values followed by true values. The answer lies between 1 and the maximum pile size. I will use first-true binary search, keeping a known feasible upper bound. Each check is $O(n)$, and the search performs $O(\log M)$ checks, for total complexity $O(n\log M)$ and $O(1)$ extra space.”

---

Key takeaways

• Binary search applies to an ordered answer space, not only a sorted input array.
• Convert the optimization goal into a Boolean feasible(candidate) predicate.
• Prove the predicate is monotonic before using binary search.
• For minimum-sufficient-answer problems, search for the first true value.
• Derive bounds from the problem’s physical or business constraints.
• Preserve a single template’s invariant; do not mix binary-search variants.
• For Koko-style problems, the complexity is $O(n\log M)$, because each candidate evaluation scans all input values.

Next, you will combine the patterns from this module in a realistic timed coding workflow: clarifying assumptions, selecting a pattern, coding in Java, testing edge cases, and communicating complexity within a 40-minute interview window.