Advanced Binary Search Patterns

Question 1

When should you use Binary Search on Answer?

Accepted Answer

When feasibility of a value changes monotonically — Binary Search on Answer works when you can check "Is X achievable?" and the answer changes from NO to YES (or vice versa) monotonically as X increases.

Question 2

'Binary search on the answer' searches over…

Accepted Answer

Over the space of possible answer values, via monotonic feasibility — Instead of searching positions, you binary-search the candidate answer range, testing each midpoint with a feasibility predicate that is monotonic in the answer.

Question 3

For 'binary search on the answer' to be valid, the feasibility function feasible(x) must be…

Accepted Answer

Monotonic: once true, it stays true as x increases — Monotonicity guarantees a single false→true boundary, which binary search can locate. Without it, halving the answer range is unjustified.

Question 4

In 'Koko Eating Bananas' (min eating speed to finish in h hours), the search space is…

Accepted Answer

Eating speeds up to max(pile), checked via a feasibility function — As speed increases, hours-needed decreases monotonically, so binary-search speed for the smallest value satisfying hours ≤ h. Cost O(n log(maxPile)).

Question 5

'Split Array Largest Sum' / 'Capacity to Ship Packages in D Days' minimize the maximum subarray sum by…

Accepted Answer

Binary searching the candidate max-sum, using a feasibility check — The candidate answer (a capacity) is monotonic: larger cap ⇒ fewer parts. Binary-search the smallest cap whose greedy split uses ≤ k parts — O(n log(sum)).

Question 6

Searching a target in a ROTATED sorted array (no duplicates) is O(log n) because…

Accepted Answer

One half stays sorted, so you pick the right side — Comparing a[lo], a[mid], a[hi] reveals which side is sorted; check whether the target lies within that sorted side's range to choose the half — halving each step.

Question 7

Finding the median of two sorted arrays in O(log(min(m,n))) uses…

Accepted Answer

A binary search for the correct partition point — Binary search the split of the smaller array; the other split is forced by the median position. Adjust until maxLeft ≤ minRight on both sides — O(log(min(m,n))).

Question 8

The overall complexity of binary search on the answer with an O(C) feasibility check over a range R is…

Accepted Answer

Reducing it to a combined cost of O(C · log R) total — You perform O(log R) iterations, each running the O(C) feasibility check — O(C·log R). Choosing a tight range and cheap check matters.

Question 9

'Aggressive Cows' / 'Magnetic Force' (maximize the minimum gap) binary-searches the answer and uses feasible(d) =…

Accepted Answer

Placing all cows so every pair is at least d apart — Larger minimum-distance d is harder to satisfy (monotonic), so binary-search the largest d for which a greedy placement fits all cows — maximize-the-minimum pattern.

Question 10

For maximize-the-minimum problems, you search for the…

Accepted Answer

The largest value that remains feasible — Feasibility is true for small thresholds and false once too large; you want the boundary's largest true value. Minimize-the-maximum is the mirror image.

Binary search on the answer

Test your knowledge

When should you use Binary Search on Answer?

Write the code

Koko Eating Bananas

Example Cases

The short version

In more depth

Binary Search on Answer Space

When to reach for this

Interview Questions

References & Further Reading

Related topics

Love this visualization?