Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 14

Binary Search in Monotonic Spaces

Recommended resources

Hello! Welcome back to our module on Sorting and Searching Algorithms.

In the previous lesson, you learned how to implement binary search on a sorted array. You saw how its O(log n) time complexity makes it incredibly efficient for finding a specific value. The key was that the array's elements were in a fixed, monotonic order.

Today, we'll take that concept to the next level. We will move beyond searching for a value in a physical array and learn how to apply binary search to find a solution in a monotonic search space. This powerful technique, often called "Binary Search on the Answer," allows you to solve a whole class of optimization problems that might not seem like search problems at all.

From Sorted Arrays to Monotonic Properties

The magic of binary search on a sorted array works because if we check the middle element, we instantly know whether to go left or right. The property "is the value less than or greater than our target?" is monotonic.

What if we could define a similar monotonic property for the answer to a problem?

Imagine a function, let's call it is_feasible(x), that takes a potential answer x and tells us if it's a valid solution (even if not the best one). For many problems, this function has a neat property: if a value x is feasible, all values "better" than x are also feasible. This creates a predictable pattern.

Monotonic Search Space for Binary Search
This image illustrates the core idea. We have a range of possible answers. The `is_feasible(x)` function evaluates each potential answer, creating a sequence of `False` values followed by a sequence of `True` values. Our goal is to use binary search to efficiently find the boundary—the first `True`.

This is_feasible(x) function is often called a predicate function. When it's monotonic, it turns our problem into a search for the first True (or last True) in a conceptual array of boolean values.

Binary Search Intuition and Predicate Functions

This article from GeeksforGeeks introduces the idea of a 'predicate function' and how its monotonic nature is the key to applying binary search.

Please read the short sections 'What is a Monotonic Function?', 'What is a Predicate Function?', and 'How do Binary Search and Monotonic Predicate Functions relate?'. Focus on how a predicate function can create a monotonic False.../True... pattern.

The General Template for "Binary Search on the Answer"

Solving these problems follows a three-step template:

  1. Define the Search Space: Identify the range of all possible answers. What's the absolute minimum possible answer (low) and the absolute maximum (high)? This range becomes your search space.
  2. Define the Predicate Function: Create the is_feasible(value) function. This is the heart of the problem. It takes a potential answer value from your search space and returns True if it's possible to achieve the problem's goal with this value, and False otherwise. The result of this function must be monotonic over the search space.
  3. Apply Binary Search: Use a standard binary search loop to find the optimal answer within the search space.
    • If is_feasible(mid) is True, it means mid is a potential solution. We store it and try to find an even better one (e.g., a smaller one if we're minimizing, or a larger one if maximizing).
    • If is_feasible(mid) is False, mid is not a valid solution, and we must adjust our search to a range with more favorable values (e.g., larger values if mid was too small).

Let's start with a simple text-based example.

Binary Search on Answer Tutorial with Problems

The article 'Binary Search on Answer' formally defines this technique and walks through a simple problem: finding the maximum integer n such that n*n < X.

Read the sections from the beginning up to and including the Python code for the first example. Pay attention to how they establish the search space (0 to X) and the monotonic relation (mid*mid < X).

Case Study: Koko Eating Bananas (LeetCode 875)

This is a classic competitive programming problem that perfectly illustrates the "Binary Search on the Answer" technique. The goal is to find the minimum eating speed k that allows Koko to eat all bananas within a given time h.

Let's watch a video that breaks down this exact problem.

Koko Eating Bananas - Binary Search - Leetcode 875 - Python

First, let's understand the problem and see why a brute-force approach helps us think about the search space. This video from NeetCode provides a clear explanation.

Watch from 00:26 to 06:03. Focus on understanding the problem statement and the brute-force approach. What are the minimum and maximum possible values for the eating speed k? This defines our search space.

After watching, let's apply our template:

  1. Search Space:

    • What is the minimum possible speed k? It has to be at least 1. So, low = 1.
    • What is the maximum necessary speed k? If Koko eats as fast as the biggest pile, she is guaranteed to finish each pile in at most one hour. So, high = max(piles).
    • Our search space for the answer is [1, max(piles)].

  2. Predicate Function:

    • is_feasible(k): Can Koko finish all bananas within h hours if her speed is k?
    • To implement this, we calculate the total time: for each pile, the time taken is ceil(pile_size / k). We sum these times. If total_time <= h, the function returns True.
    • Monotonicity Check: If a speed k is feasible, is a speed k+1 also feasible? Yes, a faster speed will always take less or equal time. This confirms our predicate is monotonic, producing a False, False, ..., True, True, True pattern. Our goal is to find the first True.

Now, let's see how to implement the binary search to find this minimum k.

Koko Eating Bananas - Binary Search - Leetcode 875 - Python

Continuing with the NeetCode video, let's see how binary search is applied to efficiently find the optimal k.

Watch from 06:03 to the end (14:58). Pay close attention to the logic inside the loop: When a valid k is found (hours <= h), why is the result updated and the search moved to the left (right = k - 1)? The Python implementation uses math.ceil(). A common trick in competitive programming to get the ceiling of a / b using integer division is (a + b - 1) // b. Keep this in your toolkit!

The logic you saw is key: when we find a feasible speed k, we know it's a possible answer. But since we want the minimum feasible speed, we record k and then try to find an even smaller one by searching in the left half of our remaining search space.

Test your understanding!

Suppose for the Koko problem, piles = [30, 11, 23, 4, 20] and h = 5. The search space for k is [1, 30].

Let's say in our binary search, mid becomes 15. Is k=15 a feasible speed?

  • Pile 1 (30): ceil(30/15) = 2 hours
  • Pile 2 (11): ceil(11/15) = 1 hour
  • Pile 3 (23): ceil(23/15) = 2 hours
  • Pile 4 (4): ceil(4/15) = 1 hour
  • Pile 5 (20): ceil(20/15) = 2 hours

The total time is 2+1+2+1+2 = 8 hours. This is greater than h=5, so is_feasible(15) is False.

How should the low and high pointers be updated for the next iteration?

Show answer

Since a speed of 15 is too slow, we need to try a faster speed. This means we must search in the right half of the current search space. The update will be low = mid + 1, which becomes low = 16.

One Concept, Many Problems

This pattern of identifying a monotonic predicate appears in many different contexts. It's not always about a simple array. To see how versatile this is, let's look at a few more classic examples.

Binary Search tutorial (C++ and Python)

This video from competitive programming expert Errichto demonstrates how to find the hidden monotonic property in several different problems, including some you might not expect.

Watch from 07:57 to 20:20. For each of the two main problems discussed (finding the first element >= X, and finding the minimum in a rotated sorted array), try to identify the 'False/True' monotonic property that he describes. What is the predicate function being checked at each mid?

As you saw, even when an array isn't perfectly sorted (like the rotated array), you can often define a predicate based on a comparison (e.g., a[mid] > a[last]) that creates the monotonic True.../False... pattern needed for binary search.

Conclusion

You've now unlocked a much more powerful application of binary search. This is a huge step forward in your competitive programming journey.

Key Takeaways:

  • Binary search can be applied to problems beyond simple sorted arrays by searching on the answer space.
  • The core requirement is a monotonic predicate function is_feasible(x) that produces a pattern like F, F, F, ..., T, T, T.
  • The general strategy involves:
    1. Defining the search space for the answer (low, high).
    2. Implementing the is_feasible(mid) check.
    3. Using binary search to find the "boundary" between False and True, which corresponds to the optimal answer.
  • Keep an eye out for problems that ask for the "minimum possible maximum" or "maximum possible minimum," as they are often candidates for this technique.

Up Next:

We've covered two fundamental search concepts. Now, we'll switch gears to sorting. In the next lesson, we will dive into Merge Sort, a classic sorting algorithm that, like binary search, uses a "divide and conquer" strategy. A solid understanding of sorting is critical, as many advanced algorithms rely on having sorted data to work efficiently.