15.15 Binary Search on Answer

Problem

Some problems ask for an optimal value rather than a specific object.

Examples:

What is the minimum machine speed needed to finish all jobs within 8 hours?
What is the smallest capacity truck that can transport all packages in 5 days?
What is the largest minimum distance possible between installed routers?
What is the minimum time required for a group of workers to complete a task?

A direct search may examine every possible answer:

answer = 1
answer = 2
answer = 3
...

This can be extremely expensive when the answer range is large.

Can divide and conquer help when the search space consists of values rather than array positions?

Solution

Use binary search on the answer.

The central idea is to transform an optimization problem into a sequence of decision problems.

Instead of asking:

What is the optimal answer?

ask:

Is answer X feasible?

If feasibility changes monotonically, binary search can locate the boundary.

This turns many optimization problems into logarithmic searches.

The Monotonicity Requirement

Binary search on the answer works when the feasibility function has the form:

false false false false
true  true  true  true

or:

true  true  true  true
false false false false

There must be a single transition point.

For example:

capacity = 5   -> impossible
capacity = 6   -> impossible
capacity = 7   -> impossible
capacity = 8   -> possible
capacity = 9   -> possible
capacity = 10  -> possible

Once a capacity becomes sufficient, every larger capacity is also sufficient.

This monotonicity creates the divide-and-conquer opportunity.

Example: Shipping Packages

Suppose packages have weights:

[3, 2, 2, 4, 1, 4]

We want the smallest ship capacity that allows delivery within:

3 days

Possible capacities:

1 ... 16

Instead of testing all values:

1
2
3
...
16

we binary search.

Feasibility Function

Given a candidate capacity:

capacity = X

simulate shipping.

Pseudo-code:

days = 1
load = 0

for package:
    if load + package > X
        days++
        load = 0

    load += package

return days <= limit

The function returns:

true

if the capacity works.

Otherwise:

false

Binary Search Structure

Once feasibility is available:

func BinarySearchAnswer(
    low, high int,
    feasible func(int) bool,
) int {
    for low < high {
        mid := low + (high-low)/2

        if feasible(mid) {
            high = mid
        } else {
            low = mid + 1
        }
    }

    return low
}

This code finds the smallest feasible value.

The optimization problem becomes a divide-and-conquer search over the answer space.

Visualizing the Search

Suppose:

capacity
1 2 3 4 5 6 7 8 9 10
F F F F F F F T T T

Binary search evaluates:

mid = 5

Result:

false

Discard:

1..5

Search:

6..10

mid = 8

Result:

true

Discard:

8..10

Search:

6..8

Continue until the boundary is found.

Divide-and-Conquer Perspective

The search interval:

[low, high]

is repeatedly divided in half.

At each step:

mid

splits the remaining answer space.

One side is discarded entirely.

This gives the recurrence:

$$ T(n)=T(n/2)+O(1) $$

leading to:

$$ O(\log n) $$

search iterations.

If the feasibility test costs:

$$ F(n) $$

then total complexity becomes:

$$ O(F(n)\log R) $$

where (R) is the size of the answer range.

Example: Router Placement

Suppose houses are located at:

[1, 2, 8, 12, 17]

Install:

3 routers

Maximize the minimum distance between routers.

The optimization question:

largest minimum distance?

becomes:

Can we place routers
with minimum spacing D?

Feasibility:

place first router

greedily place others
whenever distance >= D

count routers placed

If three routers can be placed:

true

Otherwise:

false

Distances form a monotonic search space:

D=3 -> true
D=4 -> true
D=5 -> true
D=6 -> false
D=7 -> false

Binary search finds the transition.

Example: Machine Production Time

Suppose machines require:

2
3
7

minutes per product.

Question:

minimum time to make
100 products?

Feasibility:

products produced in time T

=
T/2 + T/3 + T/7

Check:

>= 100 ?

Again the function is monotonic.

More time never produces fewer products.

Binary search identifies the minimum feasible time.

Continuous Binary Search

Sometimes the answer is a real number.

Example:

square root

We seek:

$$ x $$

such that:

$$ x^2 = n $$

Feasibility:

mid^2 <= n ?

Binary search can operate on floating-point intervals:

for i := 0; i < 100; i++ {
    mid := (low + high) / 2

    if mid*mid <= n {
        low = mid
    } else {
        high = mid
    }
}

After sufficient iterations, the interval becomes arbitrarily small.

This is sometimes called bisection search.

Integer Overflow

Computing:

mid := (low + high) / 2

may overflow.

Safer:

mid := low + (high-low)/2

This formulation is standard practice.

Finding Maximum Feasible Answers

Sometimes we want:

largest feasible value

instead of:

smallest feasible value

Example:

largest minimum distance

Then:

if feasible(mid) {
    low = mid
} else {
    high = mid - 1
}

The search direction changes, but the principle remains identical.

Complexity Analysis

Suppose:

answer range = 1..10^9

Binary search performs:

$$ \log_2(10^9) $$

iterations.

Approximately:

checks.

Even an expensive feasibility test becomes practical when called only a few dozen times.

General complexity:

$$ O(F(n)\log R) $$

where:

(F(n)) = feasibility cost
(R) = answer range

Common Applications

Scheduling

Examples:

minimum completion time
minimum workers required
minimum machine speed

Allocation

Examples:

load balancing
resource distribution
server capacity planning

Geometry

Examples:

largest minimum distance
smallest enclosing radius
placement optimization

Numerical Methods

Examples:

root finding
approximation
optimization

Competitive Programming

Many difficult-looking optimization problems reduce directly to binary search on the answer.

Common Mistakes

Missing Monotonicity

Without monotonic behavior:

true false true false

binary search is invalid.

Always verify the transition property.

Searching the Wrong Range

A poor initial range may exclude the true answer.

Establish correct lower and upper bounds first.

Incorrect Feasibility Logic

Most bugs occur inside the check function, not inside binary search itself.

Test feasibility independently.

Infinite Loops

Updating:

low = mid

instead of:

low = mid + 1

may prevent progress.

Pay careful attention to interval invariants.

Overflow

Use:

low + (high-low)/2

for midpoint calculation.

Relationship to Divide and Conquer

Unlike merge sort or quick sort, binary search on the answer does not divide the input.

It divides the solution space.

The recursion occurs over candidate answers rather than data elements.

This broader interpretation is important. Divide and conquer is not limited to arrays, trees, or matrices. Any problem with a searchable monotonic structure can often be transformed into a recursive search over possibilities.

Discussion

Binary search on the answer is one of the most valuable problem-solving techniques because it converts optimization into decision making. Instead of directly constructing the best solution, we repeatedly ask whether a candidate solution is feasible. Monotonicity then allows divide and conquer to eliminate half of the remaining possibilities at every step.

The technique appears across scheduling, numerical analysis, resource allocation, networking, and computational geometry. Experienced algorithm designers often look for monotonicity before considering more complicated approaches. A problem that initially appears to require dynamic programming, greedy optimization, or exhaustive search may reduce to a simple feasibility test combined with logarithmic divide-and-conquer search.

The next section explores another powerful divide-and-conquer application: Fast Fourier Transform (FFT), where recursive decomposition transforms polynomial multiplication from a quadratic operation into one of the most important near-linear algorithms in computer science.