What does binary search on the answer mean?

Instead of searching an array, you search the range of possible answers and test each candidate with a yes/no check. It works when the check is monotonic: once a value is feasible, every larger (or smaller) value is too.

What is the time complexity?

O(log(range) * cost of the check). For a typical feasibility check that scans n items, that is O(n log(range)).

How do I choose the lower and upper bounds?

The lower bound is the smallest value that could possibly work and the upper bound is a value that definitely works, such as the sum of all items. Getting them wrong either misses the answer or wastes iterations.

How do I find the minimum feasible value versus the maximum?

For a minimum, when the check passes set hi = mid and otherwise lo = mid + 1. For a maximum, mirror it and round mid up so the loop cannot stall.

How do I know when this pattern applies?

Look for phrases like minimise the maximum, maximise the minimum, or smallest value such that. If you can write a greedy check for one candidate, you can binary search over candidates.

What is the most common mistake?

Using a check that is not monotonic, which makes the search discard the wrong half. Test the check on a few values by hand before trusting the loop.

Binary search on the answer, not the array

Interview QuestionsBy Ashish JangraUpdated 25 October 2026

There is no array to search here. The trick is that feasibility is monotonic: if a capacity works, every larger one works too. So the answers form a sorted sequence of no-no-no-yes-yes, and binary search finds the boundary — with an O(n) feasibility check in place of an array lookup.

Binary searchCoding problemMedium

Step through it

Speed

What to watch

The thing being searched is a range of answers, not the input.
Each probe costs a full O(n) pass — the feasibility check.
The predicate flips exactly once, which is what makes it searchable.

Say this out loud

"I binary search the answer rather than an array. The predicate is 'can this capacity finish in D days', which I can check in one pass, and it is monotonic - if a capacity works, anything bigger works. So the feasible capacities are a suffix, and I search for the first one. Bounds are max weight to total weight, so it is O(n log sum)."

def min_capacity(weights, D): """Smallest ship capacity that delivers every package within D days.""" def days_needed(capacity): days, load = 1, 0 for w in weights: if load + w > capacity: # greedy: start a new day days += 1 load = 0 load += w return days lo, hi = max(weights), sum(weights) # must fit one package; one day at most probes = [] while lo < hi: mid = (lo + hi) // 2 d = days_needed(mid) probes.append((mid, d, d <= D)) if d <= D: hi = mid # this works, so nothing larger is needed else: lo = mid + 1 # too slow, so rule it and everything below out return lo, probes, days_needed weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] D = 5 answer, probes, days_needed = min_capacity(weights, D) print("weights:", weights, " D =", D) print() print("capacity | days | feasible") for cap, d, ok in probes: print(f" {cap:>5} | {d:>3} | {'yes' if ok else 'no'}") print() print("smallest capacity that works:", answer)

def min_capacity(weights, D): def days_needed(capacity): days, load = 1, 0 for w in weights: if load + w > capacity: days += 1 load = 0 load += w return days lo, hi = max(weights), sum(weights) probes = [] while lo < hi: mid = (lo + hi) // 2 d = days_needed(mid) probes.append((mid, d, d <= D)) if d <= D: hi = mid else: lo = mid + 1 return lo, probes, days_needed weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] D = 5 answer, probes, days_needed = min_capacity(weights, D) # Monotonicity is what licenses the search. Check it explicitly. print() print("the predicate flips exactly once:") for cap in range(answer - 3, answer + 3): d = days_needed(cap) print(f" capacity {cap:>2} -> {d} days,", "feasible" if d <= D else "not feasible") candidates = sum(weights) - max(weights) + 1 print() print(f"brute force: {candidates} capacities from {max(weights)} to {sum(weights)}") print(f"binary search: {len(probes)} probes, each an O(n) pass")

import math def min_speed(piles, hours): def hours_needed(speed): return sum(math.ceil(p / speed) for p in piles) lo, hi = 1, max(piles) while lo < hi: mid = (lo + hi) // 2 if hours_needed(mid) <= hours: hi = mid else: lo = mid + 1 return lo piles = [30, 11, 23, 4, 20] print("piles:", piles) for h in (5, 6, 8): s = min_speed(piles, h) print(f" finish in {h} hours -> speed {s:>2}", f"(takes {sum(math.ceil(p/s) for p in piles)} hours)") print("same structure: a monotonic predicate, checked in O(n), searched in log")

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Binary search on the answer, not the array

Step through it

What to watch

Say this out loud

Overview

Run it

Recognising it

The three things to establish before writing the loop

Cost, and the shape of it

The same shape, four other questions

Edge cases to raise

Sources and next steps

How the code works

How the code works

Change one thing

Where this runs

Check yourself