Binary Search on the Answer Space

The Core Idea: Searching for an Answer, Not an Element

The magic of binary search works because of a predictable, ordered property. In a sorted array, if you're at mid and your target is smaller, you know for sure it's to the left.

We can apply the same logic to a range of potential answers to a problem, provided the problem has a monotonic property. A function is monotonic if it's consistently non-decreasing or non-increasing.

For many optimization problems, we can define a feasible(x) function that asks, "Is it possible to achieve a solution with value x?". This function often creates a monotonic sequence of False and True values. For example, if we want to find the minimum possible value that works, our feasibility function might look like this:

[False, False, False, ..., True, True, True]

Our goal becomes finding the first True in this implicit array of boolean values.

Let's formalize this.

Now, let's apply this powerful pattern to a classic problem.

Case Study 1: Koko Eating Bananas

This problem is a perfect, intuitive example of "minimizing a maximum" (or in this case, minimizing a rate). The goal is to find the minimum eating speed K that allows Koko to finish all bananas within a given time H.

Let's watch a detailed breakdown of the problem.

Step 1: Defining the Search Space

Instead of searching the piles array, we'll search for the answer K (bananas per hour). What's the possible range for K?

• low: The slowest possible speed is 1 banana per hour. Any slower doesn't make sense.
• high: The fastest Koko ever needs to eat is determined by the largest pile. If the largest pile is M bananas, an eating speed greater than M provides no additional benefit for that pile compared to a speed of M (it still takes 1 hour). So, the maximum value in the piles array is a reasonable upper bound.

So, our answer K lies somewhere in the range [1, max(piles)].

Step 2: The isPossible(speed) Check Function

This is the heart of the solution. We need a function that, for a given speed, tells us if it's possible to eat all bananas within H hours.

The logic is straightforward:

1. Initialize totalTime = 0.
2. Iterate through each pile p in the piles array.
3. Calculate the time taken for that pile: time = ceil((double)p / speed). In integer arithmetic, a clever way to compute the ceiling ceil(a/b) is (a + b - 1) / b.
4. Add this time to totalTime.
5. After checking all piles, if totalTime <= H, return true. Otherwise, return false.

Step 3: Applying Binary Search

Now we combine the search space and the check function.

1. Initialize low = 1, high = max(piles).
2. Initialize a variable ans to store the best possible speed found so far.
3. Loop while low <= high:
   • Calculate mid = low + (high - low) / 2.
   • If isPossible(mid) is true:
     • This mid speed works! It's a potential answer.
     • We want the minimum possible speed, so let's see if we can do even better (slower).
     • Store this answer: ans = mid.
     • Search the left half: high = mid - 1.
   • If isPossible(mid) is false:
     • This mid speed is too slow. We need to eat faster.
     • Search the right half: low = mid + 1.

The final value in ans will be our answer.

Code Implementation

Here's how this would look in Java:

public class KokoEatingBananas {

    // Check function: is it possible to finish in H hours with a given speed?
    public static boolean isPossible(int[] piles, int speed, int H) {
        long totalTime = 0; // Use long to avoid overflow if piles are large
        for (int p : piles) {
            // Calculate time for this pile: ceil(p / speed)
            totalTime += (p + speed - 1) / speed;
        }
        return totalTime <= H;
    }

    public static int minEatingSpeed(int[] piles, int H) {
        int low = 1;
        int high = 0;
        for (int p : piles) {
            high = Math.max(high, p);
        }

        int ans = high; // A valid speed is guaranteed to exist

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (mid == 0) { // Avoid division by zero
                low = 1;
                continue;
            }
            if (isPossible(piles, mid, H)) {
                ans = mid; // This is a possible answer, try for a smaller one
                high = mid - 1;
            } else {
                low = mid + 1; // Speed is too slow, must increase
            }
        }
        return ans;
    }
}

The time complexity of isPossible is O(N) where N is the number of piles. We call this function O(log M) times, where M is the maximum value in the piles. The total time complexity is O(N * log M), a massive improvement over a brute-force linear scan.

Case Study 2: Allocate Books

Let's tackle a more complex problem that follows the same pattern: "minimize the maximum". The goal is to allocate books to a set number of students such that the maximum number of pages assigned to any single student is minimized.

Step 1: Defining the Search Space

What is the range for our answer (the maximum number of pages a student can be assigned)?

• low: The answer cannot be smaller than the largest book in the array. Even if a student gets only one book, they must be able to handle the largest one. So, low = max(array).
• high: In the worst/most generous allocation, one student gets all the books. So, high = sum(array).

Our answer lies in the range [max(array), sum(array)].

Step 2: The canAllocate(maxPages) Check Function

Given a potential answer maxPages (the maximum pages any student is allowed), can we allocate all books to M students?

We can determine this greedily:

1. Initialize studentsNeeded = 1 and currentPages = 0.
2. Iterate through the books:
   • For each book, if currentPages + bookPages <= maxPages, add it to the current student's load: currentPages += bookPages.
   • If it exceeds the limit, the current student can't take this book. Give it to a new student: increment studentsNeeded and set currentPages = bookPages.
3. After iterating through all books, if studentsNeeded <= M, it means the allocation is possible with the given maxPages limit. Return true.

Step 3: Applying Binary Search

The binary search logic is nearly identical to the Koko problem:

1. If canAllocate(mid) is true:
   • This mid value is a possible solution. We want to find an even smaller maximum.
   • Store the answer: ans = mid.
   • Search the left half: high = mid - 1.
2. If canAllocate(mid) is false:
   • The mid limit is too restrictive, we needed too many students. We must allow students to carry more pages.
   • Search the right half: low = mid + 1.

The time complexity is O(N * log(S)), where N is the number of books and S is the sum of all pages (the size of our search space).

Conclusion

Today you've unlocked a powerful problem-solving paradigm. By reframing optimization problems, you can leverage the O(log n) efficiency of binary search in a much broader context than just searching in arrays. This is a huge step forward for your competitive programming and technical interview preparation.

Key Takeaways:

• Binary Search on the Answer is a technique for optimization problems, often identified by "minimize the maximum" or "maximize the minimum" phrasing.
• The core requirement is a monotonic check function that validates a potential answer. This creates a [False, ..., True, ...] pattern that binary search can exploit.
• The three-step process is:
  1. Define the Search Space: Determine the absolute lowest and highest possible values for the answer.
  2. Implement a Check Function: Write a function isPossible(value) that returns true or false. This function typically runs in linear time.
  3. Apply Binary Search Template: Use the check function to guide the binary search in the defined search space, shrinking the range until you find the optimal value.

Preview of the next lesson:
We will now circle back to applying binary search on arrays, but with a twist. In the next lesson, you will learn to "Solve problems on rotated sorted arrays using a modified binary search." This is another classic interview problem that forces you to think critically about how binary search's core principles can be adapted when the array isn't perfectly sorted.