One of the most important variation of standard Binary Search is applying this technique on the answer space where the solutions for the problem statement lies.
In other words, if you have to solve a problem P, and if we can determine the solution for P will be a number between [a, b] where a and b are Numbers ,then we can apply Binary Search on the range [a, b] as by definition of Decimal Number System ,this range [a, b] is sorted!!
Let’s understand this concept via Koko eating Bananas . In this we are required to find the “minimum integer k such that she can eat all the bananas within h hours”.
Input Given : An array of integers called piles where piles[i] is the number of bananas in pile i
Need to find minimum speed of eating banana k such that all bananas in every pile is finished within h hours
For example : **Input:** piles = [3,6,7,11], h = 8 We are required to finish eating all bananas (3+6+7+11 = 27) within 8 hours!! We need to find the minimum speed for eating such that Koko finishes 27 bananas in 8 hours.
We can determine the range for the possible answer for this :
Minimum bananas Koko can eat in one hour(as speed is defined as number of bananas eaten per hour) —> 1
Maximum bananas Koko can eat in one hour —> Maximum bananas present in a pile
By above reasoning, for our Koko example , range for solution is : [1 , 11]
So we can apply Binary Search on [1, 11] and find the minimum speed of eating for Koko such that all 27 bananas are eaten within 8 hours !!!😎
The last bit of the logic is writing the isPossible() method. For our Koko example we can use below pseudo-code:
Solution template to solve this pattern of questions
Final thoughts
You can apply this concept on problems where:
It is possible to come up with a range for the final answer
Have strategy or condition mentioned in question to check correctness of different values from the answer space (isPossible() method)
Practice problems for this concept
Koko eating Bananas
Allocate Minimum Number of Pages
Maximum Candies Allocated to K children
Binary Search in Forest