16.04Beginner / Intermediate6 topics25 min4 interactive animations

Binary search over answer

Some problems ask for the smallest or largest value that satisfies a condition, rather than the position of a value. If the condition is monotonic, you can binary search the answer itself and test each guess with a fast greedy check.

Learning goals

Recognise a monotonic feasibility predicate
Pick the answer range [lo, hi] and the right mid rounding
Solve minimise-the-maximum and maximise-the-minimum problems
Write the greedy feasibility check for each classic problem

Prerequisites

Lower boundGreedy reasoningPrefix sums are helpful

“What is the slowest speed that still finishes on time?” Trying every speed works but is slow. If speed s works, every faster speed also works, so you can binary search the speed.

16.04.1

Monotonic feasibility

A predicate ok(x) is monotonic if once it becomes true it stays true (false, false, true, true, …), or the reverse. Binary search then finds the boundary in O(log range) calls to ok.

Template for “smallest x that works”: if ok(mid), set hi = mid; otherwise lo = mid + 1. For “largest x that works”, round mid up and set lo = mid or hi = mid - 1. Rounding up prevents an infinite loop when hi = lo + 1.

Java

1// smallest x in [lo, hi] with ok(x) == true
2while (lo < hi) {
3    int mid = lo + (hi - lo) / 2;
4    if (ok(mid)) hi = mid;
5    else lo = mid + 1;
6}
7return lo;
8
9// largest x in [lo, hi] with ok(x) == true
10while (lo < hi) {
11    int mid = lo + (hi - lo + 1) / 2;   // round up
12    if (ok(mid)) lo = mid;
13    else hi = mid - 1;
14}
15return lo;

Worst

O(log(range) × cost of ok)

Space

O(1)

16.04.2

Minimum possible maximum

“Split the work so the largest share is as small as possible” is the most common answer-search shape. If a limit L is achievable, any larger limit is too, so the predicate is monotonic.

The answer lies between the largest single item (no share can be smaller) and the total (one share takes everything). The check greedily fills each share up to L and counts how many shares it needs.

Book allocation, ship capacity and split-array-largest-sum all have this shape.
The greedy check is O(n), so the whole solution is O(n log(sum)).

16.04.3

Allocate books

Given pages per book in order and k students, give each student a contiguous block of at least one book and minimise the maximum pages any student reads. If there are more students than books, there is no valid allocation.

The animation shows each feasibility check by colouring the books by the student who reads them.

Allocate minimum pages (book allocation)

Interactive · edit the input

Answer space [90, 203]

90203

Input

12346790

Remaining windowKnown to workKnown to fail

Setup

Split the books into 2 contiguous parts and minimise the largest part. Every answer lies in [90, 203], and feasibility is monotonic, so binary search the answer itself.

Step 1 / 31

Java

1public static int allocateBooks(int[] pages, int students) {
2    if (students > pages.length) return -1;
3    int lo = max(pages), hi = sum(pages);
4    while (lo < hi) {
5        int mid = lo + (hi - lo) / 2;
6        if (studentsNeeded(pages, mid) <= students) {
7            hi = mid;
8        } else {
9            lo = mid + 1;
10        }
11    }
12    return lo;
13}
14
15static int studentsNeeded(int[] pages, int limit) {
16    int need = 1, sum = 0;
17    for (int p : pages) {
18        if (sum + p > limit) { need++; sum = 0; }
19        sum += p;
20    }
21    return need;
22}

Live state

0 feasibility checks

203

No condition evaluated on this step

Execution trace (dry run table)Show 31 steps

Step	Line	State	What happens
1	L3	k=2 lo=90 hi=203	Split the books into 2 contiguous parts and minimise the largest part. Every answer lies in [90, 203], and feasibility is monotonic, so binary search the answer itself.
2	L4	k=2 lo=90 hi=203	114 candidate answers remain.
3	L5	k=2 lo=90 hi=203 mid=146	mid = 146.
4	L6	k=2 lo=90 hi=203 mid=146	146 works. Every larger value works too, so try smaller.
5	L7	k=2 lo=90 hi=146	hi = 146.
6	L4	k=2 lo=90 hi=146	57 candidate answers remain.
7	L5	k=2 lo=90 hi=146 mid=118	mid = 118.
8	L6	k=2 lo=90 hi=146 mid=118	118 works. Every larger value works too, so try smaller.
9	L7	k=2 lo=90 hi=118	hi = 118.
10	L4	k=2 lo=90 hi=118	29 candidate answers remain.
11	L5	k=2 lo=90 hi=118 mid=104	mid = 104.
12	L6	k=2 lo=90 hi=118 mid=104	104 fails. Every smaller value fails too.
13	L9	k=2 lo=105 hi=118	lo = 105.
14	L4	k=2 lo=105 hi=118	14 candidate answers remain.
15	L5	k=2 lo=105 hi=118 mid=111	mid = 111.
16	L6	k=2 lo=105 hi=118 mid=111	111 fails. Every smaller value fails too.
17	L9	k=2 lo=112 hi=118	lo = 112.
18	L4	k=2 lo=112 hi=118	7 candidate answers remain.
19	L5	k=2 lo=112 hi=118 mid=115	mid = 115.
20	L6	k=2 lo=112 hi=118 mid=115	115 works. Every larger value works too, so try smaller.
21	L7	k=2 lo=112 hi=115	hi = 115.
22	L4	k=2 lo=112 hi=115	4 candidate answers remain.
23	L5	k=2 lo=112 hi=115 mid=113	mid = 113.
24	L6	k=2 lo=112 hi=115 mid=113	113 works. Every larger value works too, so try smaller.
25	L7	k=2 lo=112 hi=113	hi = 113.
26	L4	k=2 lo=112 hi=113	2 candidate answers remain.
27	L5	k=2 lo=112 hi=113 mid=112	mid = 112.
28	L6	k=2 lo=112 hi=113 mid=112	112 fails. Every smaller value fails too.
29	L9	k=2 lo=113 hi=113	lo = 113.
30	L4	k=2 lo=113 hi=113	lo == hi == 113. The answer is pinned down.
31	L12	k=2 return=113	return 113. 2 students <= 2. Found with 7 checks instead of testing all 114 values.

16.04.4

Aggressive cows

Place c cows in stalls at given positions so the minimum distance between any two cows is as large as possible. This is the maximise-the-minimum mirror of the previous problems.

After sorting, greedily place a cow in the first stall, then in each next stall that is at least gap away. If that fits c cows, gap works and so does every smaller gap.

Aggressive cows (maximise the minimum distance)

Interactive · edit the input

Setup

Sort the positions so the greedy check can walk left to right.

Step 1 / 16

Java

1public static int aggressiveCows(int[] stalls, int cows) {
2    Arrays.sort(stalls);
3    int lo = 1, hi = stalls[stalls.length - 1] - stalls[0];
4    while (lo < hi) {
5        int mid = lo + (hi - lo + 1) / 2;       // round up
6        if (canPlace(stalls, cows, mid)) {
7            lo = mid;
8        } else {
9            hi = mid - 1;
10        }
11    }
12    return lo;
13}
14
15static boolean canPlace(int[] stalls, int cows, int gap) {
16    int placed = 1, last = stalls[0];
17    for (int i = 1; i < stalls.length; i++) {
18        if (stalls[i] - last >= gap) { placed++; last = stalls[i]; }
19    }
20    return placed >= cows;
21}

Live state

0 feasibility checks

No condition evaluated on this step

Execution trace (dry run table)Show 16 steps

Step	Line	State	What happens
1	L2	k=3	Sort the positions so the greedy check can walk left to right.
2	L3	k=3 lo=1 hi=8	Place 3 cows so the closest pair is as far apart as possible. Every answer lies in [1, 8], and feasibility is monotonic, so binary search the answer itself.
3	L4	k=3 lo=1 hi=8	8 candidate answers remain.
4	L5	k=3 lo=1 hi=8 mid=5	mid = 5. Round up so lo = mid always makes progress.
5	L6	k=3 lo=1 hi=8 mid=5	5 fails. Every larger value fails too.
6	L9	k=3 lo=1 hi=4	hi = 4.
7	L4	k=3 lo=1 hi=4	4 candidate answers remain.
8	L5	k=3 lo=1 hi=4 mid=3	mid = 3. Round up so lo = mid always makes progress.
9	L6	k=3 lo=1 hi=4 mid=3	3 works. Every smaller value works too, so try larger.
10	L7	k=3 lo=3 hi=4	lo = 3.
11	L4	k=3 lo=3 hi=4	2 candidate answers remain.
12	L5	k=3 lo=3 hi=4 mid=4	mid = 4. Round up so lo = mid always makes progress.
13	L6	k=3 lo=3 hi=4 mid=4	4 fails. Every larger value fails too.
14	L9	k=3 lo=3 hi=3	hi = 3.
15	L4	k=3 lo=3 hi=3	lo == hi == 3. The answer is pinned down.
16	L12	k=3 return=3	return 3. 3 cows fit >= 3. Found with 3 checks instead of testing all 8 values.

16.04.5

Capacity to ship

Packages must ship in their given order within D days. Find the smallest ship capacity that makes this possible.

The answer lies between the heaviest package and the total weight. The check loads each day until the next package would overflow, then starts a new day.

Capacity to ship packages within D days

Interactive · edit the input

Answer space [10, 55]

1055

Input

12345678910

Remaining windowKnown to workKnown to fail

Setup

Find the smallest ship capacity that delivers every package, in order, within 5 days. Every answer lies in [10, 55], and feasibility is monotonic, so binary search the answer itself.

Step 1 / 23

Java

1public static int shipWithinDays(int[] weights, int days) {
2    int lo = max(weights), hi = sum(weights);
3    while (lo < hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (daysNeeded(weights, mid) <= days) {
6            hi = mid;
7        } else {
8            lo = mid + 1;
9        }
10    }
11    return lo;
12}
13
14static int daysNeeded(int[] weights, int cap) {
15    int need = 1, load = 0;
16    for (int w : weights) {
17        if (load + w > cap) { need++; load = 0; }   // start a new day
18        load += w;
19    }
20    return need;
21}

Live state

0 feasibility checks

No condition evaluated on this step

Execution trace (dry run table)Show 23 steps

Step	Line	State	What happens
1	L2	k=5 lo=10 hi=55	Find the smallest ship capacity that delivers every package, in order, within 5 days. Every answer lies in [10, 55], and feasibility is monotonic, so binary search the answer itself.
2	L3	k=5 lo=10 hi=55	46 candidate answers remain.
3	L4	k=5 lo=10 hi=55 mid=32	mid = 32.
4	L5	k=5 lo=10 hi=55 mid=32	32 works. Every larger value works too, so try smaller.
5	L6	k=5 lo=10 hi=32	hi = 32.
6	L3	k=5 lo=10 hi=32	23 candidate answers remain.
7	L4	k=5 lo=10 hi=32 mid=21	mid = 21.
8	L5	k=5 lo=10 hi=32 mid=21	21 works. Every larger value works too, so try smaller.
9	L6	k=5 lo=10 hi=21	hi = 21.
10	L3	k=5 lo=10 hi=21	12 candidate answers remain.
11	L4	k=5 lo=10 hi=21 mid=15	mid = 15.
12	L5	k=5 lo=10 hi=21 mid=15	15 works. Every larger value works too, so try smaller.
13	L6	k=5 lo=10 hi=15	hi = 15.
14	L3	k=5 lo=10 hi=15	6 candidate answers remain.
15	L4	k=5 lo=10 hi=15 mid=12	mid = 12.
16	L5	k=5 lo=10 hi=15 mid=12	12 fails. Every smaller value fails too.
17	L8	k=5 lo=13 hi=15	lo = 13.
18	L3	k=5 lo=13 hi=15	3 candidate answers remain.
19	L4	k=5 lo=13 hi=15 mid=14	mid = 14.
20	L5	k=5 lo=13 hi=15 mid=14	14 fails. Every smaller value fails too.
21	L8	k=5 lo=15 hi=15	lo = 15.
22	L3	k=5 lo=15 hi=15	lo == hi == 15. The answer is pinned down.
23	L11	k=5 return=15	return 15. 5 days <= 5. Found with 5 checks instead of testing all 46 values.

16.04.6

Koko eating bananas

Koko eats at most k bananas per hour from one pile and must finish all piles within h hours. Find the minimum k.

A pile of p bananas takes ceil(p / k) hours, written in integer maths as (p + k - 1) / k. Feasibility is monotonic in k, and k never needs to exceed the largest pile.

Koko eating bananas

Interactive · edit the input

Answer space [1, 11]

111

Input

36711

Remaining windowKnown to workKnown to fail

Setup

Find the slowest eating speed that finishes all piles within 8 hours. Every answer lies in [1, 11], and feasibility is monotonic, so binary search the answer itself.

Step 1 / 19

Java

1public static int minEatingSpeed(int[] piles, int h) {
2    int lo = 1, hi = Arrays.stream(piles).max().getAsInt();
3    while (lo < hi) {
4        int mid = lo + (hi - lo) / 2;
5        if (hoursNeeded(piles, mid) <= h) {
6            hi = mid;
7        } else {
8            lo = mid + 1;
9        }
10    }
11    return lo;
12}
13
14static long hoursNeeded(int[] piles, int k) {
15    long hours = 0;
16    for (int p : piles) hours += (p + k - 1) / k;   // ceil(p / k)
17    return hours;
18}

Live state

0 feasibility checks

No condition evaluated on this step

Execution trace (dry run table)Show 19 steps

Step	Line	State	What happens
1	L2	k=8 lo=1 hi=11	Find the slowest eating speed that finishes all piles within 8 hours. Every answer lies in [1, 11], and feasibility is monotonic, so binary search the answer itself.
2	L3	k=8 lo=1 hi=11	11 candidate answers remain.
3	L4	k=8 lo=1 hi=11 mid=6	mid = 6.
4	L5	k=8 lo=1 hi=11 mid=6	6 works. Every larger value works too, so try smaller.
5	L6	k=8 lo=1 hi=6	hi = 6.
6	L3	k=8 lo=1 hi=6	6 candidate answers remain.
7	L4	k=8 lo=1 hi=6 mid=3	mid = 3.
8	L5	k=8 lo=1 hi=6 mid=3	3 fails. Every smaller value fails too.
9	L8	k=8 lo=4 hi=6	lo = 4.
10	L3	k=8 lo=4 hi=6	3 candidate answers remain.
11	L4	k=8 lo=4 hi=6 mid=5	mid = 5.
12	L5	k=8 lo=4 hi=6 mid=5	5 works. Every larger value works too, so try smaller.
13	L6	k=8 lo=4 hi=5	hi = 5.
14	L3	k=8 lo=4 hi=5	2 candidate answers remain.
15	L4	k=8 lo=4 hi=5 mid=4	mid = 4.
16	L5	k=8 lo=4 hi=5 mid=4	4 works. Every larger value works too, so try smaller.
17	L6	k=8 lo=4 hi=4	hi = 4.
18	L3	k=8 lo=4 hi=4	lo == hi == 4. The answer is pinned down.
19	L11	k=8 return=4	return 4. 8h <= 8h. Found with 4 checks instead of testing all 11 values.

Practice ladder

Now try it yourself

Easy

Square root of an integer (floor)
First bad version

Medium

Koko eating bananas
Capacity to ship packages within D days
Minimum days to make m bouquets

Advanced

Split array largest sum
Aggressive cows
Painter's partition
Kth smallest number in a multiplication table

Key takeaways

If ok(x) is monotonic, binary search the answer instead of the array.
Bound the answer tightly, write an O(n) greedy check, and choose mid rounding to match the update rule.
Total cost is O(n log(range)).