Binary Search on Monotonic Answer Spaces

Hello! Welcome to your next lesson in the "Advanced Algorithmic Patterns" module.

In our previous lesson on 2D Dynamic Programming, we tackled complex problems like Longest Common Subsequence by breaking them down into a grid of overlapping subproblems. This showed how to find optimal solutions by building up from smaller, simpler states.

Today, we'll explore a completely different, yet equally powerful, optimization strategy: solving problems by applying binary search on a monotonic answer space. You're undoubtedly familiar with using binary search to find an element in a sorted array. Here, we'll elevate that concept to search for an optimal answer within a range of possibilities, even when there's no explicit array to search. This is a common and highly efficient pattern for a specific class of optimization problems that you'll encounter in interviews.

---

1. The Core Idea: Searching the Answer, Not the Input

Standard binary search works because a sorted array has a monotonic property: arr[i] <= arr[i+1]. This allows us to discard half of the search space with a single comparison.

The insight for today's lesson is that many optimization problems have a similar monotonic property, but it applies to the potential answers rather than the input data itself.

Imagine a function, is_feasible(x), that tells you whether an answer x is possible. If we can find a range of possible answers [min_answer, max_answer] where this function behaves monotonically, we can use binary search to find the optimal answer.

Let's formalize this.

This pattern is especially useful for problems that ask for the "minimum possible maximum" or "maximum possible minimum" of some value. Let's see it in action.

---

2. A Classic Example: Koko Eating Bananas

This problem is a canonical example of binary searching on the answer space.

Problem Statement: Koko has n piles of bananas. The i-th pile has piles[i] bananas. She has h hours to eat all of them. She can choose her eating speed, k (bananas per hour). In each hour, she chooses a pile and eats k bananas. If a pile has fewer than k bananas, she eats them all and doesn't move to another pile in that same hour. What is the minimum integer k such that she can eat all the bananas within h hours?

Step 1: Analyze the Brute-Force Approach

The most straightforward approach is to test every possible speed k, starting from 1. For each k, we calculate the total time required. The first k that allows Koko to finish within h hours is our answer.

This linear scan works, but it can be very slow if the required speed is large. This inefficiency hints that a better search method exists.

Step 2: Identify the Monotonic Property and Define the Search Space

Let's think about the is_feasible(k) function: "Is it possible to finish all bananas in h hours with a speed of k?"

Notice the monotonic property: if Koko can finish with a speed of k, she can definitely finish with any speed k' > k. Conversely, if she fails with speed k, she will also fail with any speed k' < k.

This creates the False, ..., False, True, ..., True pattern we saw earlier. We can use binary search!

But what are we searching? The answer space of possible speeds, k.

• Minimum possible speed (low): 1. Koko must eat at least one banana per hour.
• Maximum possible speed (high): The max(piles). If Koko's speed is equal to the size of the largest pile, she is guaranteed to finish each pile in exactly one hour. Any speed higher than this doesn't help further.

Step 3: Implement the Binary Search

Now we have all the components:

1. Search Space: [1, max(piles)]
2. Feasibility Check: A function can_finish(k) that calculates the total hours for speed k and returns True if total_hours <= h. The time to finish one pile p is ceil(p / k), which can be calculated in integer arithmetic as (p + k - 1) // k.
3. Binary Search Logic:
   • Pick a mid speed from [low, high].
   • If can_finish(mid) is True: mid is a possible answer. But we want the minimum speed, so we try to find an even smaller one. We store mid as our best answer so far and search the left half: high = mid - 1.
   • If can_finish(mid) is False: The speed is too slow. We must increase it. We search the right half: low = mid + 1.

The following video provides a crystal-clear walkthrough of this entire process.

Here is a clean Python implementation reflecting this logic.

import math

class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:



        # Step 1: Define the search space for the answer 'k'
        low = 1
        high = max(piles)
        min_k = high # Initialize result with a valid (but not optimal) speed

        while low <= high:
            mid_k = low + (high - low) // 2
            



            # Step 2: Implement the feasibility function
            total_hours = 0
            for p in piles:



                # math.ceil(p / mid_k)
                total_hours += (p + mid_k - 1) // mid_k
            



            # Step 3: Adjust search space based on feasibility
            if total_hours <= h:



                # This speed is feasible. It's a potential answer.
                # Try for an even smaller k.
                min_k = mid_k
                high = mid_k - 1
            else:



                # This speed is too slow. Need to increase k.
                low = mid_k + 1
                
        return min_k




# Time Complexity: O(N * log(M)), where N is the number of piles and M is the max value in piles.
# The binary search performs log(M) iterations, and each iteration involves a feasibility check
# that takes O(N) time to iterate through all piles.
# Space Complexity: O(1).

---

3. Generalizing the Pattern and Writing Production-Quality Code

The "Koko" problem is just one application. Let's generalize this into a reusable template.

Given your background in Rust, you'll appreciate how this pattern can be applied there as well. A very simple example is calculating the integer square root of a number x. The answer lies in the range [0, x], and the feasibility function mid * mid <= x is monotonic.

Writing Robust Code

In a production environment, correctness and robustness are paramount. Simply getting the logic right isn't enough. Here are common pitfalls to avoid.

These details—preventing overflow, ensuring loop termination, and handling boundaries correctly—are what distinguish a basic solution from a production-quality one.

---

4. Another Example: Shipping Packages

To solidify your understanding, let's look at one more problem that follows the exact same pattern: "Capacity to Ship Packages within D Days" (LeetCode 1011).

Problem: You have a list of package weights and must ship them in order within D days. Find the minimum capacity a ship must have to do this.

This is structurally identical to the Koko problem:

• What are you searching for? The minimum ship capacity (the answer).
• What is the search space? low = max(weights), high = sum(weights).
• What is the feasibility function? can_ship(capacity): Given a capacity, can we ship all packages in order within D days?

The video below walks through this problem, reinforcing the pattern.

---

Conclusion

You've now added a powerful and non-obvious algorithmic tool to your arsenal. Binary search on the answer space is a versatile technique for optimization problems that might otherwise seem to require a slower, linear search.

Key Takeaways:

• Look for Monotonicity: The key signal for this pattern is a monotonic relationship between a potential answer and its feasibility. If making an answer "better" (e.g., faster speed, larger capacity) makes it more likely to be feasible, binary search is on the table.
• Define the Holy Trinity: To solve these problems, you must clearly define:
  1. The answer space (low and high bounds).
  2. The feasibility function (is_feasible(mid)).
  3. The pointer update logic (do you search left or right when feasible?).
• Complexity: This pattern typically improves a solution from O(N * M) (linear scan) to O(N * log M), where M is the size of the answer range and N is the work needed for the feasibility check.
• Robustness is Key: Production-quality implementations require careful handling of integer overflow, loop conditions, and pointer updates to avoid subtle bugs.

Next Lesson Preview

In our next lesson, we will explore another clever pattern that leverages a specific data structure: "Solve 'next greater element' style problems efficiently using a monotonic stack." This will shift our focus to problems involving finding the next element in a sequence that satisfies a certain condition, a common pattern in signal processing and data analysis.