Binary Search on the Answer: Find the Smallest Valid Value

By Hourly DSA · October 1, 2026 · 3 min read

Binary search can find the smallest value that makes a condition true, even when there is no sorted array to search. The requirement is a predictable boundary: once a candidate works, every larger candidate must work too.

The difficult part is usually explaining that condition. Halving the search range comes afterward.

Turn an optimization question into a yes-or-no question

Suppose packages have weights [2, 3, 4, 5]. You must ship them in order within three days. Each day's total weight cannot exceed the ship's capacity, and a package cannot be split.

What is the smallest capacity that works?

Instead of guessing the minimum directly, ask: can capacity C finish within three days?

For capacity 5, the daily groups are [2, 3], [4], and [5]. That works. Capacity 4 fails immediately because the last package weighs 5.

The answer is 5, but the reasoning should also work for inputs where the answer isn't so obvious.

Why the condition is monotonic

If capacity 5 works, capacity 6 also works: you can reuse exactly the same daily groups. Increasing capacity never invalidates an existing schedule.

Across candidate capacities, the answers therefore look like:

capacity:  3      4      5     6     7
works:     false  false  true  true  true

There is one boundary between failure and success. Binary search finds its first true value.

This argument depends on the actual rules. If the question required every day to be filled exactly to capacity, larger values would not necessarily preserve a valid schedule. Don't assume every numerical optimization problem has this shape.

Check one capacity with a scan

For a candidate capacity, keep loading the current day while the next package fits. Otherwise, start another day. Reject any capacity below the heaviest package.

This scan uses the fewest days possible for that capacity. Its first day takes the longest prefix that fits; no valid schedule can put more packages on that day. Apply the same reasoning to the remaining packages.

For capacity 7, the groups are [2, 3], [4], and [5]. For capacity 9, they are [2, 3, 4] and [5]. Both finish within three days.

The check should accept at most three days. Requiring exactly three would change the question unnecessarily.

Choose bounds that include the answer

The lower bound is the largest package, 5. The upper bound is the total weight, 14: that capacity ships everything in one day.

Maintain an inclusive range containing the smallest valid capacity:

while left < right:
    mid = left + floor((right - left) / 2)
    if works(mid): right = mid
    else: left = mid + 1

Starting with [5, 14], test 9, then 7, then 6, then 5. All work, so the right boundary keeps moving left until both boundaries equal 5.

Keep mid when it works because it might be the first valid answer. Discard it when it fails because monotonicity rules out every smaller value too.

Account for the check's cost

With n packages and R integer candidates in the initial range, the method takes O(n log(R + 1)) time and O(1) auxiliary space. Each feasibility scan costs O(n); binary search does not make that work disappear.

The broader pattern appears in minimum speeds, maximum loads, and scheduling limits. First define a candidate, then prove the yes-or-no answers have one boundary.

Test the boundary

If the same packages must arrive within two days, does capacity 7 work?

No. It still needs three groups. Capacity 8 also needs three: [2, 3], [4], and [5]. Capacity 9 works with [2, 3, 4] and [5], so 9 is the smallest valid answer.

Small counterexamples make good Hourly DSA practice: state the condition, try one candidate, and justify which half you can discard.