7.07Beginner5 topics12 min4 interactive animations

Counting and searching answer

When a problem asks for the smallest or largest value that makes something possible, and the possible values are ordered, you can search over the answer itself. This lesson collects the pattern; the full treatment with animations is in Chapter 16.

Learning goals

Write a feasibility check for a candidate answer
Recognise a monotone predicate and its boundary
Combine binary search on the answer with a greedy check
Use a fixed number of iterations for real-valued answers

Prerequisites

Binary searchGreedy reasoning

“What is the slowest speed that still gets me there on time?” You can test any speed quickly, and if a speed works every faster one works too. That is all binary search needs.

7.07.1

Feasibility check

Split the problem into two parts: “is answer x achievable?” and “which x is optimal?”. The first is often a simple greedy pass; the second is a search over x.

A good check is fast (usually O(n)), returns a plain boolean, and does not try to find the optimum itself. In the Koko animation below, each check computes the hours needed at one speed.

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.

7.07.2

Monotone predicate

A predicate ok(x) is monotone if it is false, false, …, then true, true, … (or the reverse). Then exactly one boundary separates the two, and binary search finds it in O(log range) checks.

Always argue monotonicity before searching. If a larger capacity can ever make a schedule infeasible, binary search returns a wrong answer without any error.

Problem	Predicate ok(x)	Direction
Koko eating bananas	finishes within h hours at speed x	false… then true…
Ship within D days	capacity x ships everything in D days	false… then true…
Aggressive cows	cows fit with minimum gap x	true… then false…

7.07.3

Binary search on answer

Pick bounds [lo, hi] that certainly contain the answer, then run lower-bound binary search on ok. For the smallest feasible x: if ok(mid) set hi = mid, otherwise lo = mid + 1.

Total cost is O(log(hi − lo)) feasibility checks. The animation for capacity to ship packages shows the remaining window shrink and the known-good and known-bad regions grow.

Java

1int lo = minPossible, hi = maxPossible;
2while (lo < hi) {
3    int mid = lo + (hi - lo) / 2;
4    if (ok(mid)) hi = mid;      // mid works: the answer is mid or smaller
5    else lo = mid + 1;          // mid fails: the answer is larger
6}
7return lo;

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.

7.07.4

Greedy feasibility

The check is usually greedy: fill a day, a student or a container as much as allowed, then start the next one, and count how many you used. Greedy is correct here because filling as much as possible never hurts the later groups.

For “maximise the minimum gap” (aggressive cows), place each item as early as the gap allows. Placing earlier leaves more room for the rest.

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.

7.07.5

Precision binary search

For real-valued answers there is no next value, so update with lo = mid or hi = mid and stop by precision. A fixed number of iterations (60 to 100) is the safest stopping rule because it always terminates, even when floating-point rounding stalls the interval.

Change epsilon in the square-root animation to see how the number of halvings grows by about 3.3 for each extra decimal digit.

Square root by bisection

Interactive · edit the input

Answer space [0, 10]

010

Remaining windowKnown to workKnown to fail

Setup

√10 is somewhere in [0, 10]. hi is at least 1 so the range also covers x < 1.

Step 1 / 33

Java

1public static double sqrt(double x, double eps) {
2    double lo = 0, hi = Math.max(1, x);
3    while (hi - lo > eps) {
4        double mid = (lo + hi) / 2;
5        if (mid * mid < x) {
6            lo = mid;
7        } else {
8            hi = mid;
9        }
10    }
11    return (lo + hi) / 2;
12}

Live state

0 iterations

eps

0.01

No condition evaluated on this step

Execution trace (dry run table)Show 33 steps

Step	Line	State	What happens
1	L2	x=10 eps=0.01 lo=0 hi=10	√10 is somewhere in [0, 10]. hi is at least 1 so the range also covers x < 1.
2	L3	x=10 eps=0.01 lo=0 hi=10 width=10	The interval is still wider than eps.
3	L5	x=10 eps=0.01 lo=0 hi=10 mid=5 mid*mid=25	mid is at or above the root, the root is to the left.
4	L8	x=10 eps=0.01 lo=0 hi=5	hi = 5.
5	L3	x=10 eps=0.01 lo=0 hi=5 width=5	The interval is still wider than eps.
6	L5	x=10 eps=0.01 lo=0 hi=5 mid=2.5 mid*mid=6.25	mid is too small, the root is to the right.
7	L6	x=10 eps=0.01 lo=2.5 hi=5	lo = 2.5.
8	L3	x=10 eps=0.01 lo=2.5 hi=5 width=2.5	The interval is still wider than eps.
9	L5	x=10 eps=0.01 lo=2.5 hi=5 mid=3.75 mid*mid=14.0625	mid is at or above the root, the root is to the left.
10	L8	x=10 eps=0.01 lo=2.5 hi=3.75	hi = 3.75.
11	L3	x=10 eps=0.01 lo=2.5 hi=3.75 width=1.25	The interval is still wider than eps.
12	L5	x=10 eps=0.01 lo=2.5 hi=3.75 mid=3.125 mid*mid=9.76563	mid is too small, the root is to the right.
13	L6	x=10 eps=0.01 lo=3.125 hi=3.75	lo = 3.125.
14	L3	x=10 eps=0.01 lo=3.125 hi=3.75 width=0.625	The interval is still wider than eps.
15	L5	x=10 eps=0.01 lo=3.125 hi=3.75 mid=3.4375 mid*mid=11.81641	mid is at or above the root, the root is to the left.
16	L8	x=10 eps=0.01 lo=3.125 hi=3.4375	hi = 3.4375.
17	L3	x=10 eps=0.01 lo=3.125 hi=3.4375 width=0.3125	The interval is still wider than eps.
18	L5	x=10 eps=0.01 lo=3.125 hi=3.4375 mid=3.28125 mid*mid=10.7666	mid is at or above the root, the root is to the left.
19	L8	x=10 eps=0.01 lo=3.125 hi=3.28125	hi = 3.28125.
20	L3	x=10 eps=0.01 lo=3.125 hi=3.28125 width=0.15625	The interval is still wider than eps.
21	L5	x=10 eps=0.01 lo=3.125 hi=3.28125 mid=3.20313 mid*mid=10.26001	mid is at or above the root, the root is to the left.
22	L8	x=10 eps=0.01 lo=3.125 hi=3.20313	hi = 3.20313.
23	L3	x=10 eps=0.01 lo=3.125 hi=3.20313 width=0.07813	The interval is still wider than eps.
24	L5	x=10 eps=0.01 lo=3.125 hi=3.20313 mid=3.16406 mid*mid=10.01129	mid is at or above the root, the root is to the left.
25	L8	x=10 eps=0.01 lo=3.125 hi=3.16406	hi = 3.16406.
26	L3	x=10 eps=0.01 lo=3.125 hi=3.16406 width=0.03906	The interval is still wider than eps.
27	L5	x=10 eps=0.01 lo=3.125 hi=3.16406 mid=3.14453 mid*mid=9.88808	mid is too small, the root is to the right.
28	L6	x=10 eps=0.01 lo=3.14453 hi=3.16406	lo = 3.14453.
29	L3	x=10 eps=0.01 lo=3.14453 hi=3.16406 width=0.01953	The interval is still wider than eps.
30	L5	x=10 eps=0.01 lo=3.14453 hi=3.16406 mid=3.1543 mid*mid=9.94959	mid is too small, the root is to the right.
31	L6	x=10 eps=0.01 lo=3.1543 hi=3.16406	lo = 3.1543.
32	L3	x=10 eps=0.01 lo=3.1543 hi=3.16406 width=0.00977	The interval is narrower than eps, so stop.
33	L11	x=10 eps=0.01 return=3.15918	return 3.15918 (Math.sqrt gives 3.16228). Error is under eps after 10 halvings.

Practice ladder

Now try it yourself

Easy

Sqrt(x) by binary search
First bad version

Medium

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

Advanced

Split array largest sum
Magnetic force between two balls
Minimize max distance to gas station

Key takeaways

Separate “is x feasible?” from “which x is best?”.
Prove the predicate is monotone, bound the answer, then binary search it.
Greedy checks make each probe O(n); real-valued answers use a fixed iteration count.