Lesson 11.4 · Binary Search

Binary Search on the Answer

When you can check "is x enough?" and bigger x is always at least as good, binary search the smallest x that works.

15 min

Think of it like this

Choosing the slowest walking speed that still gets you to the train in time: if 4 km/h works, every faster speed works too. So test speeds by halving, instead of trying every speed.

1.Monotonic feasibility

Write a function feasible(x) that answers yes or no. If it's false for small x and true from some point on, binary search finds the first true x with the same template as the lower bound, over the range of possible answers instead of indexes.

The cost is O(log(range) × cost of feasible). For speeds up to 10⁹ that's about 30 checks.

Koko.java

public class Main {
    // can Koko eat all piles within h hours at speed k?
    static boolean feasible(int[] piles, int h, int k) {
        long hours = 0;
        for (int p : piles) hours += (p + k - 1) / k;     // ceiling of p / k
        return hours <= h;
    }
    public static void main(String[] args) {
        int[] piles = {3, 6, 7, 11};
        int h = 8, lo = 1, hi = 11, checks = 0;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            checks++;
            if (feasible(piles, h, mid)) hi = mid; else lo = mid + 1;
        }
        System.out.println("slowest speed = " + lo + " after " + checks + " checks");
    }
}

Output

slowest speed = 4 after 4 checks

2.Spotting it

Phrases like "minimum capacity", "smallest maximum", "largest minimum", "fewest days such that" are strong hints, especially when the answer range is huge but checking one candidate is easy.

Remember

Need a yes/no check that flips once.
Search the answer range with the first-true template.
Ceiling division: (p + k − 1) / k.

Common mistakes

Choosing a range that doesn't include the answer (e.g. starting at 0 when 0 is invalid).
Integer overflow when summing hours (use long).

Command Palette

Binary Search on the Answer

1.Monotonic feasibility

2.Spotting it