Skip to content
Tutorials Center
My learning

Topics

Lesson 75 of 225 ยท Searching

Binary Search on the Answer

Learn to binary search on the answer in Python: monotonic yes/no checks, integer square root, Koko eating bananas, split array largest sum, maximising a minimum, and floats.

So far you searched a list. This lesson searches something stranger: the set of possible answers. You are not given a sorted array at all. You are given a question like "what is the smallest eating speed that finishes the pile of bananas in time?" and you notice that if a speed works, any faster speed also works. That one observation, a monotonic yes/no property, lets you binary search over the possible speeds and solve in logarithmic many guesses what looks like an optimisation puzzle.

This pattern, often called binary search on the answer, is one of the most useful tricks in interviews and contests. It turns "find the best value" into "repeatedly ask: is this value good enough?". Checking one value is usually easy, even when finding the best value directly is hard.

The recipe

TEXT
answer candidates:  1   2   3   4   5   6   7   8   9  ...
feasible(x)?        no  no  no  no yes yes yes yes yes
                                    ^
                          smallest feasible = the answer
  1. Define the answer space: the smallest and largest value the answer could possibly be (lo, hi).
  2. Write feasible(x): can we succeed if the answer is x? It must be monotonic: all "no" then all "yes" (or the reverse).
  3. Binary search for the boundary: the smallest x where feasible(x) is true.

The loop is the same template you met in binary search variants:

Python
def smallest_feasible(lo: int, hi: int, feasible) -> int:
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid          # mid works; maybe something smaller does too
        else:
            lo = mid + 1      # mid fails; so does everything smaller
    return lo

Cost: O(log(hi - lo)) calls to feasible, each costing whatever the check costs, usually O(n). The total is typically O(n log range).

Always prove monotonicity before you use this pattern. If a larger value can be feasible while a smaller one is not and then a still-larger one is infeasible again, the "discard half" step throws away the answer and the search returns garbage.

Warm-up: integer square root

Problem. Compute floor(sqrt(n)) without math.sqrt.

Brute force. Try 0, 1, 2, ... until i * i > n: O(sqrt(n)) steps.

Binary search on the answer. The question "is x * x <= n?" is yes for small x and no for large x. We want the largest x that is yes. To reuse the "smallest feasible" template, flip it: find the smallest x where x * x > n, then subtract one.

Python Integer square root by binary search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Koko eating bananas

Problem. There are piles of bananas, piles = [3, 6, 7, 11]. A guard returns in h = 8 hours. Each hour Koko picks one pile and eats up to k bananas from it (if the pile has fewer, she wastes the rest of the hour). Find the smallest integer speed k that finishes in time.

Brute force. Try k = 1, 2, 3, ... and compute the hours each time. If the biggest pile is m, that is up to m guesses, each costing O(n).

Observation. If speed k works, any speed above k also works (monotonic!). The answer lies between 1 and max(piles). The hours needed at speed k are sum(ceil(p / k) for p in piles), computed with the integer-ceiling trick (p + k - 1) // k.

Python Koko eating bananas: linear guess versus binary search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each tuple is (answer, number of guesses). The binary search uses at most about log2(max pile) guesses, around 20 for a million-banana pile, while the brute-force count grows with the answer itself.

Split array largest sum

Problem. Split an array of positive integers into m non-empty contiguous pieces so that the largest piece sum is as small as possible. Example: [7, 2, 5, 10, 8] with m = 2.

Brute force. Try every way to cut: exponential or heavy dynamic programming.

Binary search on the answer. Guess the largest allowed piece sum limit. Then check greedily: walk through the array, starting a new piece whenever adding the next item would exceed limit. If you needed at most m pieces, limit is feasible. Feasibility is monotonic: a larger limit never needs more pieces. The answer is between max(nums) (a piece must hold the biggest item) and sum(nums) (one piece holds everything).

TEXT
nums = [7, 2, 5, 10, 8], m = 2
limit = 15: [7,2,5] [10] ... then 8 doesn't fit in 10+8=18 > 15 -> third piece -> 3 pieces > 2  NO
limit = 18: [7,2,5] [10,8]                                     -> 2 pieces        YES
Python Split array largest sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time: O(n log(sum)). The same check solves "ship packages within D days" and "painter's partition": replace "piece" by "day" or "painter".

Maximising a minimum

The recipe also works in the other direction. Problem (aggressive cows). Place c cows in stalls at positions on a line so that the minimum distance between any two cows is as large as possible.

Feasibility of distance d: greedily put a cow in the first stall, then in the next stall that is at least d away, and so on. If you can place c cows, d is feasible. Smaller d is easier, so feasibility is "yes, yes, yes, no, no": we want the largest feasible d. Use the mirror template: when feasible(mid), move lo = mid (keep it) and use an upper midpoint (lo + hi + 1) // 2 to avoid an infinite loop.

Python Maximise the minimum distance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answer space can be continuous, such as "the square root of 2" or "the time at which two trains meet". You cannot step by 1, so you stop when the interval is small enough, or simply run a fixed number of iterations (each halves the interval, so 60 iterations shrink any reasonable interval below the precision of a float). Using lo == hi as the stop condition is a trap: floats may never become exactly equal.

Python Floating-point binary search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

K-th element of two sorted arrays, and the median of a row-sorted matrix

The median-of-two-arrays partition trick generalizes to any rank k. To find the k-th smallest (1-based) of two sorted arrays a and b, binary search how many items i to take from a; then k - i come from b. A split is correct when the last item taken from each side is no bigger than the first item left on the other side. Always search on the shorter array.

Python K-th smallest of two sorted arrays

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The time is O(log min(n, m)). The median follows directly: for an odd total take the middle rank, for an even total average the two middle ranks.

Median of a row-wise sorted matrix

Take a matrix with r rows and c columns where every row is sorted, but the rows are not sorted against each other. Flattening and sorting costs O(rc log(rc)). Instead binary search on the answer: the median is the smallest value x such that at least (r*c + 1) // 2 entries are <= x. Counting the entries <= x takes one bisect_right per row.

Python Median of a row-wise sorted matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cost is O(r log c log(max - min)). It is the same recipe as the problems above: define a yes/no test that is monotonic in x, then search for the boundary.

How to spot the pattern

Look for these signals in a problem statement:

  • It asks for the minimum of a maximum, or the maximum of a minimum ("minimise the largest", "maximise the smallest").
  • It asks for the smallest or largest value that satisfies a condition (speed, capacity, time, distance, size).
  • You can answer "does value x work?" in O(n) or O(n log n) with a greedy scan.
  • Larger (or smaller) values only ever make the check easier.
Problem Candidates feasible(x)
Koko eating bananas speed 1..max pile hours at speed x <= h
Ship within D days capacity max..sum days needed with capacity x <= D
Split array largest sum limit max..sum pieces needed <= m
Aggressive cows distance 1..span cows placeable at distance x >= c
Integer square root 0..n x * x <= n

Common mistakes

  • Wrong search bounds: lo too high skips the answer, hi too low cuts it off. Reason about the smallest and largest conceivable answer.
  • Non-monotonic check. Test feasible on a few values and print the yes/no row before trusting it.
  • Infinite loop when maximising: with lo = mid you must use the upper midpoint (lo + hi + 1) // 2.
  • Floating-point equality. Loop a fixed number of times or until hi - lo < eps.
  • Slow feasible. The total cost is the check's cost times the number of guesses; keep the check linear.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What property must the feasibility check have for binary search on the answer to work?

    Monotonic yes/no answers form a boundary that binary search can find. Without monotonicity, discarding half of the candidates can discard the answer.
  2. 2. Koko's piles are [3, 6, 7, 11] and she has 8 hours. How many hours does speed 4 need?

    ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1 + 2 + 2 + 3 = 8 hours, so speed 4 just fits in 8 hours.
  3. 3. When maximising the answer with 'if feasible: lo = mid', which midpoint avoids an infinite loop?

    With lo = mid and the lower middle, a range of two values never shrinks. The upper middle always moves lo forward or hi down.
  4. 4. What is the time complexity of split-array-largest-sum by binary search on the answer?

    About log2(sum) guesses, each requiring one O(n) greedy pass.
  5. 5. Why prefer a fixed iteration count over 'while lo != hi' in floating-point binary search?

    Rounding means the interval can stop shrinking without lo == hi. A fixed count of halvings (or an epsilon test) always terminates.

Summary

  • Binary search can search a range of possible answers when a yes/no question about a candidate is monotonic.
  • Recipe: bound the answer, write feasible(x) (usually a greedy O(n) scan), binary search the boundary.
  • Minimising uses hi = mid / lo = mid + 1; maximising uses lo = mid with the upper midpoint.
  • Classics: integer square root, Koko eating bananas, ship packages, split array largest sum, aggressive cows.
  • For real-valued answers, run a fixed number of halvings or stop at a small epsilon.
  • Total cost is (number of guesses, about log of the range) x (cost of one check).

Next: Jump, Exponential, Interpolation and Ternary Search