Binary Search on Answer

Hello! In our previous lessons, we've honed our binary search skills on various structures—from simple sorted arrays to more complex rotated arrays and even 2D matrices. The common thread was always leveraging some form of order to efficiently eliminate half of the search space.

Today, we'll take this powerful idea one step further into a more abstract, but extremely common, interview pattern. We will move from searching for an element within a data structure to searching for an answer within a range of possible solutions. Your goal is to learn how to apply binary search to find an optimal value (like a minimum speed or maximum capacity) when the feasibility of any given value exhibits a monotonic property. This powerful technique is often called "binary search on the answer."

The Core Idea: Searching the Solution Space

So far, our binary search has looked like this:

1. Take a sorted array A.
2. Pick the middle element A[mid].
3. Compare A[mid] to our target and decide whether to search left or right.

"Binary search on the answer" reframes this process:

1. Define a range of possible answers, [low, high].
2. Pick a candidate answer from the middle, mid.
3. Check if mid is a feasible solution to the problem. Based on the result, decide whether the true optimal answer lies in the lower or upper half of the range.

This works only if the problem has a monotonic property. What does that mean? It means that if a candidate answer k works, then any "better" candidate (e.g., a larger one if we're maximizing, or a smaller one if we're minimizing in some contexts) will also work. Conversely, if k is not a feasible answer, then any "worse" candidate won't be feasible either.

The table below from GeeksforGeeks shows where this pattern fits. We're focusing on the cases where the input isn't necessarily sorted, but the problem's solution space exhibits a monotonic function.

A Simple Introductory Example

Let's ground this with a simple problem. Imagine we need to find the largest integer n such that $n^2<101$.

A brute-force approach would be to check n=1, 2, 3, ... until the condition fails. This is slow, taking $O(X)$ time.

A better way is to recognize the monotonic property.

• Search Space: The answer n must be between 0 and 101. So, our search space is [0, 101].
• Feasibility Check: For a given candidate mid, is mid * mid < 101?
• Monotonicity: If mid is a valid answer (e.g., mid=5, since $5^2<101$), then any integer smaller than mid is also valid. If mid is not a valid answer (e.g., mid=11, since $11^2>101$), then any integer larger than mid is also not valid. This gives us a clear signal to shrink our search space.

The following resource walks through this exact thought process, from brute-force to the optimized binary search approach.

A Classic Interview Problem: Koko Eating Bananas

Now let's apply this to a realistic LeetCode problem. This problem is a perfect showcase for binary search on the answer.

Problem: Koko the monkey loves bananas. There are N piles of bananas, piles[i] is the number of bananas in the i-th pile. Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses a pile and eats k bananas. If the pile has fewer than k bananas, she eats them all and won't eat any more during that hour. Koko wants to finish all bananas within h hours. What is the minimum integer k such that she can eat all the bananas within h hours?

To get a firm grasp of the problem, the following video gives a wonderful visual explanation.

The brute-force approach of checking every speed k from 1 upwards is too slow if the potential speeds are very high. This is where binary search on the answer shines.

Let's define our components for binary search:

1. The "Answer" to Search For: The minimum eating speed, k.
2. The Search Space [low, high]:
   • What's the lowest possible speed? low = 1.
   • What's the highest necessary speed? high = max(piles). Any speed greater than the largest pile is wasteful; it doesn't speed up eating that pile any further (since Koko waits for the hour to finish).
3. The Monotonic Feasibility Function: Let's define can_finish(k) as a function that returns true if Koko can finish all bananas within h hours at speed k, and false otherwise. This function is monotonic:
   • If can_finish(k) is true, then can_finish(k+1) must also be true (a faster speed can only help).
   • If can_finish(k) is false, then can_finish(k-1) must also be false (a slower speed will certainly not be enough).

This monotonic behavior is exactly what we need. We can now binary search for the smallest k for which can_finish(k) is true.

The same video has a fantastic segment illustrating this optimization.

From Logic to Code

Now, how do we implement this? The core of the algorithm is a binary search loop that calls our can_finish(k) helper function. A key detail is correctly updating our answer variable and shrinking the search space.

If can_finish(mid) is true:

• This mid speed is a possible answer. We should record it.
• But we are looking for the minimum possible speed. So, let's try to find an even smaller speed that works. We shrink our search space to the lower half: high = mid - 1.

If can_finish(mid) is false:

• This mid speed is too slow. We must increase our speed.
• We shrink our search space to the upper half: low = mid + 1.

This DEV Community article provides a great JavaScript template and explanation for this pattern.

To see the code in action with a step-by-step dry run, let's return to the video one last time.

Recognizing the Pattern in the Wild

You've now seen the pattern in detail. A crucial skill for interviews is identifying when to use it. Here are the main giveaways:

• The problem asks you to find the minimum or maximum value that satisfies a certain condition (e.g., "minimum speed", "maximum capacity").
• The relationship between the candidate answer and its feasibility is monotonic. If you can do it with X, you can surely do it with X+1 (or X-1, depending on the problem).
• The range of possible answers is large, making a linear check (brute-force) too slow.

Another classic example is "Capacity to Ship Packages Within D Days" (LeetCode 1011). The problem is to find the minimum capacity of a ship to transport all packages within D days. The logic is nearly identical to Koko's problem: you binary search on the ship's capacity. The video resource LINK covers this problem, and you may find it helpful for extra practice.

The GeeksforGeeks article also provides a handy list of keywords.

Conclusion

In this lesson, we've unlocked a very powerful and abstract application of binary search. It's a significant step beyond searching for elements in an array and is a staple of competitive programming and technical interviews.

Here are your key takeaways:

• Binary search is not just for arrays: It can be applied to any problem where you are searching for an answer within a range, provided there is a monotonic feasibility property.
• The General Template:
  1. Define the Search Space: Identify the absolute minimum (low) and maximum (high) possible values for the answer.
  2. Create a Feasibility Function: Write a helper function is_feasible(candidate) that checks if a given candidate answer satisfies the problem's constraints.
  3. Binary Search: Use a standard binary search loop. Inside the loop, call is_feasible(mid). Based on the result, update your potential answer and shrink the search space (low or high) appropriately.
• Pattern Recognition: Look for problems asking for a "minimum of a maximum" or "maximum of a minimum," where feasibility changes predictably as you vary the candidate answer.

This lesson concludes our module on Sorting and Binary Search Patterns. You've built a solid foundation, from basic sorting and searching to advanced applications. In our next module, we'll shift gears and begin exploring fundamental node-based data structures, starting with Linked Lists, Stacks, and Queues.