7.4 Search on Answer

Most binary search examples begin with a sorted array. In practice, some of the most powerful applications of binary search involve no array at all.

Instead of searching for a value inside a collection, you search for the answer itself.

This technique, commonly called binary search on answer, transforms optimization problems into decision problems. Rather than asking:

What is the optimal value?

you ask:

Is a candidate value feasible?

If feasibility is monotone, binary search can efficiently locate the optimal answer.

This pattern appears in scheduling systems, resource allocation, logistics optimization, network planning, manufacturing, cloud infrastructure, and competitive programming. Once recognized, many seemingly difficult optimization problems become straightforward applications of binary search.

Problem

Suppose you have a collection of tasks that must be completed within a limited number of days.

Each day has a maximum processing capacity.

You want to determine the smallest capacity that allows all tasks to be completed within the deadline.

Example:

Tasks: [3, 2, 2, 4, 1, 4]
Days: 3

Possible capacities:

Capacity = 4  -> impossible
Capacity = 5  -> possible
Capacity = 6  -> possible
Capacity = 7  -> possible

The smallest feasible capacity is:

A brute-force approach tests capacities one by one.

4
5
6
7
...

This becomes inefficient when the search range is large.

Solution

Define a feasibility function.

func CanShip(
	weights []int,
	days int,
	capacity int,
) bool {
	usedDays := 1
	current := 0

	for _, weight := range weights {
		if current+weight > capacity {
			usedDays++
			current = 0
		}

		current += weight
	}

	return usedDays <= days
}

Observe an important property:

Capacity = 4  -> false
Capacity = 5  -> true
Capacity = 6  -> true
Capacity = 7  -> true
Capacity = 8  -> true

The feasibility result changes exactly once.

False False False True True True True

This is a monotone predicate.

Binary search can locate the first true value.

func MinCapacity(
	weights []int,
	days int,
) int {
	lo := 0
	hi := 0

	for _, weight := range weights {
		if weight > lo {
			lo = weight
		}
		hi += weight
	}

	for lo < hi {
		mid := lo + (hi-lo)/2

		if CanShip(weights, days, mid) {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

The returned value is the smallest feasible capacity.

Understanding the Transformation

The original optimization problem asks:

Find the minimum feasible capacity.

Binary search cannot directly answer that question.

Instead, transform it into:

Is capacity X sufficient?

The answer becomes a boolean value.

Capacity 4 -> false
Capacity 5 -> true
Capacity 6 -> true
Capacity 7 -> true

Binary search requires exactly this structure.

The optimization problem disappears and is replaced by a boundary search.

Recognizing Search-on-Answer Problems

Many optimization problems share a common shape.

You are asked to find:

Minimum value satisfying a constraint

Maximum value satisfying a constraint

Examples include:

Minimum machine speed
Minimum server capacity
Minimum warehouse size
Minimum network bandwidth
Maximum production rate
Maximum achievable score
Maximum feasible distance

The key question becomes:

Can I verify a candidate answer efficiently?

If the verification function is monotone, binary search is often applicable.

Example: Cutting Wood

Suppose logs have heights:

20 15 10 17

You need at least:

7 units

of wood.

A saw cuts every log above a chosen height.

For a cut height of:

the collected wood is:

20 -> 5
15 -> 0
10 -> 0
17 -> 2

Total:

The objective is:

Find the highest possible cut height.

This can be transformed into:

Can height H produce at least 7 units?

Results:

Height 16 -> false
Height 15 -> true
Height 14 -> true
Height 13 -> true

Binary search finds the boundary.

Example: Maximum Minimum Distance

Suppose routers must be installed in houses.

1 2 4 8 9

You need:

3 routers

The objective:

Maximize the minimum distance
between installed routers.

Instead of directly maximizing distance, ask:

Can routers be placed with
minimum distance D?

Results:

Distance 2 -> true
Distance 3 -> true
Distance 4 -> true
Distance 5 -> false
Distance 6 -> false

Again, a monotone boundary appears.

The largest feasible distance can be found with binary search.

Choosing Search Bounds

One challenge in search-on-answer problems is selecting initial boundaries.

For minimum-value searches:

lo = smallest possible answer
hi = largest possible answer

For shipping capacity:

lo = max(weight)
hi = sum(weights)

No valid answer can exist below the largest package.

No answer larger than the sum is ever required.

Good bounds reduce search space and simplify correctness arguments.

Generic Framework

Most search-on-answer solutions follow the same template.

func FirstTrue(
	lo, hi int,
	ok func(int) bool,
) int {
	for lo < hi {
		mid := lo + (hi-lo)/2

		if ok(mid) {
			hi = mid
		} else {
			lo = mid + 1
		}
	}

	return lo
}

Usage:

answer := FirstTrue(
	minAnswer,
	maxAnswer,
	func(x int) bool {
		return feasible(x)
	},
)

The algorithm remains unchanged.

Only the feasibility function differs.

Correctness Reasoning

Search-on-answer problems become much easier to reason about when expressed as boundaries.

Suppose:

False False False True True True

represents feasibility.

The invariant becomes:

All values before lo are impossible.
All values at or after hi are possible.

Every iteration shrinks the unknown region.

When the interval becomes empty, the boundary has been located.

This reasoning is identical to lower-bound binary search.

Continuous Search Spaces

Search-on-answer is not limited to integers.

Suppose you need to approximate:

√50

Define:

x² ≥ 50

Values:

7.0 -> false
7.1 -> true

Binary search can repeatedly narrow the interval.

After enough iterations, the approximation reaches the desired precision.

This technique appears in geometry, physics simulation, optimization, and numerical computing.

Complexity Analysis

Assume:

Answer range = R
Feasibility cost = T

Binary search performs:

O(log R)

iterations.

Total complexity:

O(T log R)

This formula is important.

The cost of the feasibility function often dominates the running time.

A highly efficient verification function usually matters more than the binary search itself.

Common Mistakes

Many developers attempt binary search before proving monotonicity. Without a monotone feasibility function, binary search is invalid.

Another common mistake is choosing incorrect search bounds. If the optimal answer lies outside the initial interval, the algorithm may produce incorrect results.

A third mistake occurs when the feasibility function mutates shared state. Binary search assumes independent evaluations. Side effects can invalidate later checks.

Finally, some problems contain multiple transitions:

False True False True

Such predicates are not monotone and cannot be searched with standard binary search.

Takeaway

Search on answer is one of the most important applications of binary search. Rather than searching data, you search the solution space itself. The central idea is to replace an optimization problem with a monotone feasibility test, creating a boundary between impossible and possible answers. Once that boundary exists, binary search can locate the optimal value in logarithmic time. Many advanced scheduling, allocation, optimization, and planning problems are ultimately variations of this pattern.