When we think of binary search, most of us visualize searching for a target in a sorted array. But did you know you can apply binary search to a completely different realm—the solution space of a problem? This is where Binary Search on the Answer comes in, a clever and versatile pattern used to solve optimization problems.
In this blog post, we’ll explore what Binary Search on the Answer is, when to use it, and how to implement it. We’ll also look at examples to solidify your understanding.
What is Binary Search on the Answer?
Binary Search on the Answer is an algorithmic pattern where binary search is applied to a range of potential solutions (called the solution space) rather than a data array. The goal is to efficiently determine the maximum or minimum feasible value that satisfies a given condition.
Binary Search on the Answer ONLY works if:
1. Feasibility Check: You can efficiently check whether a value x satisfies the condition (usually O(n) or better).
2. Monotonicity: The solution space is divided into two zones:
• A “possible” zone where the condition holds.
• An “impossible” zone where the condition fails.
• These zones must have a clear boundary and no overlaps or breaks.
Common Use Cases
1. Minimization Problems:
• Find the smallest value x for which a condition is true.
• Example: “What is the minimum speed to complete a task within a given time?”
2. Maximization Problems:
• Find the largest value x for which a condition is true.
• Example: “What is the maximum size of a piece that meets the condition?”
Steps to Solve a Problem Using Binary Search on the Answer
1. Define the Solution Space
• Identify the range of possible answers: [low, high].
• low: The smallest possible value.
• high: The largest possible value.
int low = getMinPossibleAnswer(nums); // Define the lower bound
int high = getMaxPossibleAnswer(nums); // Define the upper bound2. Write the Feasibility Check Function
• Implement a function to check whether a value x satisfies the condition.
• Example: “Can you complete a task in x time?”
private boolean isValid(int x) {
// Define the condition to check feasibility for x
}3. Perform Binary Search
• Use binary search to iteratively narrow down the solution space:
• If the condition is satisfied for mid, adjust the search range accordingly:
• For minimization: Move towards smaller values.
• For maximization: Move towards larger values.
while (low < high) {
int mid = low + (high - low) / 2;
if (isValid(mid)) {
high = mid; // Move towards smaller values for minimization
} else {
low = mid + 1; // Move towards larger values
}
}
return low; // Final answer
Scenario: Optimizing Packing Speed
Imagine you manage a warehouse where boxes of goods need to be packed for shipping. The warehouse workers must pack all the boxes into containers before the day ends. Each worker packs boxes at a fixed speed (boxes/hour), and your goal is to determine the minimum speed required to finish all the packing within a given time.
Box sizes (batches): [30, 11, 23, 4, 20]
Total hours available: 51. Define the Range of Potential Solutions
The solution space (range of potential answers) is determined by:
1. Minimum Speed (low):
• At least 1 box/hour (if packing speed is extremely slow).
2. Maximum Speed (high):
• Equal to the largest batch size (max(piles)) because the fastest scenario would be a worker completing the largest batch in 1 hour.
int low = 1; // Minimum speed
int high = Arrays.stream(piles).max().getAsInt(); // Maximum speedSolution Space:
• [low, high] = [1, 30]
2. Feasibility Check
To verify if a maximum load x is feasible:
• For a given speed x, calculate the total hours required to pack all boxes.
• If the total hours is less than or equal to hours, the speed is valid.
private boolean isValid(int speed, int[] piles, int hours) {
int totalHours = 0;
for (int pile : piles) {
totalHours += Math.ceil((double) pile / speed); // Hours required for each batch
}
return totalHours <= hours;
}3. Binary Search to Find the Minimum Speed
With the range and feasibility check defined, binary search is used to find the smallest feasible speed x .
Steps:
1. Initialize the Search Space:
• Set left = 1 (minimum speed).
• Set right = max(piles) (maximum speed).
2. Iteratively Narrow the Range:
• Compute the midpoint:
mid = left + (right – left) / 2
• Use the feasibility check:
• If mid is feasible, reduce right = mid to explore smaller speeds.
• If mid is not feasible, increase left = mid + 1 to explore larger speeds.
3. Return the Result:
• The binary search ends when left equals right , and the minimum feasible speed is found.
public int minPackingSpeed(int[] containers, int h) {
int left = 1;
int right = Arrays.stream(containers).max().getAsInt();
while (left < right) {
int mid = left + (right - left) / 2;
if (canPackAll(containers, h, mid)) {
right = mid; // Try smaller speeds
} else {
left = mid + 1; // Try larger speeds
}
}
return left;
}Koko Eating Bananas: A Step-by-Step Guide Using Binary Search on the Answer
The Koko Eating Bananas problem (LeetCode #875) is a great example of Binary Search on the Answer, a powerful technique for solving optimization problems. Let’s break down the solution step by step, following a structured framework to help you understand and apply this algorithm pattern.
import java.util.Arrays;
public class KokoEatingBananas {
public int minEatingSpeed(int[] piles, int h) {
// Step 2: Set up the search space
int left = 1;
int right = Arrays.stream(piles).max().getAsInt();
// Step 4: Perform Binary Search
while (left < right) {
int mid = left + (right - left) / 2;
if (canEatAll(piles, h, mid)) {
right = mid; // Try smaller speeds
} else {
left = mid + 1; // Try larger speeds
}
}
// Step 5: Return the result
return left;
}
// Step 3: Decision Function
private boolean canEatAll(int[] piles, int h, int k) {
int hours = 0;
for (int pile : piles) {
hours += Math.ceil((double) pile / k);
if (hours > h) {
return false;
}
}
return true;
}
}Step 1: Define the Problem
The problem is simple: Koko loves bananas, but she must eat them all within a given number of hours, h . Each pile of bananas has a different size, and Koko eats at a constant speed k (bananas per hour). If a pile has more bananas than she can eat in an hour, she’ll take multiple hours to finish it.
Optimization Goal:
Find the minimum speed k at which Koko can eat all the bananas within h hours.
Constraints:
• k must be an integer.
• Koko can eat any positive number of bananas in an hour.
Numeric Range (Search Space):
The possible eating speeds k range between:
• Lower Bound: 1 (the slowest possible eating speed).
• Upper Bound: The size of the largest pile, since eating faster than this is unnecessary.
Step 2: Set Up the Search Space
The search space for k is initialized using the minimum and maximum feasible values:
• Lower Bound (left): 1 , as Koko can eat at least 1 banana per hour.
• Upper Bound (right): The largest pile size, as this represents the fastest speed needed to clear the largest pile in one hour.
int left = 1;
int right = Arrays.stream(piles).max().getAsInt();Step 3: Create the Decision Function
The decision function determines whether Koko can eat all the bananas within h hours at a given speed k . This function:
1. Simulates Koko’s eating process by calculating the total hours required for all piles at speed k .
2. Checks feasibility: If the total hours exceed h , k is too slow.
Key Formula:
For each pile, the hours needed to finish it is:
hours = pile size / k
private boolean canEatAll(int[] piles, int h, int k) {
int hours = 0;
for (int pile : piles) {
hours += Math.ceil((double) pile / k); // Hours for this pile
if (hours > h) {
return false; // Exceeds the allowed time
}
}
return true; // Can finish in time
}Step 4: Perform Binary Search
With the search space and decision function defined, we can perform binary search to find the smallest feasible value of k .
Steps:
1. Calculate the midpoint of the current search range:
int mid = left + (right - left) / 2;2. Use the decision function to check feasibility:
• If k = mid is feasible, reduce right to explore smaller values.
• Otherwise, increase left to explore larger values.
3. Repeat until left equals right , where the bounds converge on the optimal solution.
while (left < right) {
int mid = left + (right - left) / 2;
if (canEatAll(piles, h, mid)) {
right = mid; // Try a smaller speed
} else {
left = mid + 1; // Increase speed
}
}Step 5: Return the Result
After the binary search completes, the value of left will hold the minimum speed k at which Koko can eat all the bananas within h hours. This is returned as the result:
return left;Conclusion
Binary Search on the Answer is a powerful and versatile algorithm pattern for solving optimization problems with a numeric search space and monotonic properties. By defining the range of possible solutions, creating a feasibility check, and systematically narrowing the search space, you can efficiently find the optimal answer. This approach is not only efficient but also widely applicable, making it an essential tool for tackling complex algorithmic challenges in competitive programming and real-world scenarios.
