Binary Search on Answer Space

1. The Core Idea: Searching for an Answer, Not an Index

So far, our search space has been the indices of an array. Now, imagine the search space is the set of all possible answers to a problem. Many optimization problems can be phrased as:

• "Find the minimum value k such that a condition(k) is true."
• "Find the maximum value k such that a condition(k) is true."

If this condition(k) has a monotonic property, we can use binary search.

To understand this crucial property, let's read a short, insightful explanation.

This monotonicity is the key. If we can find a value k for which our condition is met, we know that any "less optimal" value (e.g., k+1, k+2... for a minimization problem) will also meet the condition. This creates a sorted sequence of [False, False, ..., True, True, True] across the range of possible answers. Our goal is to find the first True.

This pattern is especially useful for problems that ask to "minimize the maximum" or "maximize the minimum". These phrases are strong signals that binary search on the answer might be the intended solution.

2. The General Algorithm

To apply binary search on the answer space, we need a systematic approach. The process generally involves three main steps:

1. Define the Search Space: Determine the logical range [low, high] for the possible answers. What is the absolute minimum the answer could be? What is the absolute maximum?
2. Design a is_feasible(value) Function: This is the heart of the solution. You need to create a function that takes a potential answer (value) and checks if it's possible to satisfy the problem's constraints with that value. This check often involves a greedy approach or a simple traversal of the input data and typically runs in linear time, e.g., $O(n)$.
3. Apply Binary Search: Use the standard binary search algorithm on the range [low, high]. In each step, use the is_feasible(mid) function to decide whether to search in the lower or upper half of the answer range.
   • If is_feasible(mid) is true, it means mid is a potential answer. We can try for an even better one. For a minimization problem, we'd try smaller values, so we set high = mid - 1 and store mid as our current best answer.
   • If is_feasible(mid) is false, mid is not a valid answer. We need to aim for a less optimal value. For a minimization problem, we'd need a larger value, so we set low = mid + 1.

3. Worked Example: Koko Eating Bananas

Let's apply this framework to a classic problem: LeetCode 874. Koko Eating Bananas.

Problem Statement: Koko has n piles of bananas, piles[i]. She has h hours to eat them all. She can choose an eating speed k (bananas per hour). Each hour, she eats from a single pile. If a pile has fewer than k bananas, she eats them all and doesn't move to another pile that hour. Find the minimum integer k such that she can eat all the bananas within h hours.

This problem screams "Binary Search on the Answer"! It asks for the "minimum value k" that satisfies a condition (finishing within h hours).

The following video provides an exceptionally clear, step-by-step walkthrough of this problem. We'll go through it in sections.

Now, let's apply our three-step algorithm.

Step 1: Define the Search Space for k

What's the slowest and fastest Koko could possibly eat?

• low = 1: The minimum possible eating speed is 1 banana per hour.
• high = max(piles): The maximum speed she would ever need is the size of the largest pile. Eating faster than that provides no benefit for that pile, as she still has to spend a full hour on it. We could use an even larger upper bound (like sum(piles)), but a tighter bound is more efficient.

Our search space for the answer k is [1, max(piles)].

Step 2: Design the is_feasible(speed) function

Given a potential speed k (our mid value in the binary search), can Koko finish all bananas in h hours? To check this, we simply calculate the total time required.

For each pile p with a given speed k, the time taken is ceil(p / k). In integer arithmetic, this is (p + k - 1) // k. We sum these times for all piles. If the total_time <= h, the function returns True.

Step 3: Apply Binary Search

Now we have all the pieces. We binary search in the range [low, high].

# Python-like Pseudocode
low = 1
high = max(piles)
min_k = high

while low <= high:
    mid_k = low + (high - low) // 2
    
    # Handle the edge case of speed being 0
    if mid_k == 0:
        low = 1
        continue

    # Step 2: Check if mid_k is a feasible speed
    if is_feasible(mid_k, piles, h):
        # This speed works. It's a potential answer.
        # Let's try for an even smaller speed.
        min_k = mid_k
        high = mid_k - 1
    else:
        # This speed is too slow. We must increase it.
        low = mid_k + 1

return min_k

Watch the final part of the video to see this logic come together with a full walkthrough and code implementation.

The time complexity will be $O(N\log M)$, where N is the number of piles and M is the range of our search space (i.e., max(piles)). This is because for each step of the binary search ($\log M$), we perform a linear scan over the N piles in our is_feasible function.

Conclusion

You've now unlocked a powerful problem-solving pattern. By reframing a problem, you can turn a complex optimization task into a straightforward binary search.

Key Takeaways:

• Binary search can be used on the "answer space," not just on arrays.
• This pattern is applicable when the problem's condition function exhibits monotonicity. If a value k works, any "less optimal" value also works.
• Look for keywords like "minimize the maximum" or "maximize the minimum" as hints for this pattern.
• The core implementation requires three steps: defining the answer's search space, creating an is_feasible checker function, and applying the binary search logic to narrow down the answer.

This concludes our module on Foundational Techniques! You've covered complexity, array traversal, and several advanced binary search patterns.

In our next lesson, we will begin a new module, Array and String Patterns, starting with a fundamental and highly versatile pattern: the two-pointer technique.