How to Use Binary Search over the Solution Space
Binary search has often been an efficient tool used by programmers to solve problems separable into a certain “YES” or “NO” over some threshold. Let us try to understand how it actually works.
Binary Search at first impression looks like a simple algorithm which can only be used to search for an element of our choice with the help of some inequality operation. But more often than not, it has been used to search the right answer to some problem, by modifying the conditions of searching the space.
We can identify two separate though connected uses of Binary Search :
- To find element X
- To search for optimal answer over separable solution space
The first one is pretty basic and I assume most people are aware of it. Lets talk more about the second one. What exactly does “separable” solution space mean?
It means that we can separate our search space into two parts like “YES YES YES YES YES | NO NO NO NO NO” where YES denotes valid answer and NO denotes invalid answer, with a clear boundary between the two. We’ll solve a problem -https://www.spoj.com/problems/AGGRCOW/ to understand the concept clearly.
Problem Statement:
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).
His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ wants to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Logic: We have to assign the C cows to the N stalls such that minimum distance between any two cows is maximum. A brute force approach would be to try out recursively all the possible combinations and obtain the minimum distance which is the largest of all the combinations. But a better approach would be to use binary search over solution.
Binary Search Approach : We know that for some minimum distance X, if we are able to accommodate the C cows into the N stalls, then for all distances lesser than X also it would be possible. Similarly if for minimum distance X, if we are unable to accommodate the C cows into the N stalls, then for all distances greater than X also it would NOT be possible. This helps us to understand the relation with binary search because after each step, we can reduce the search space by half, where we are searching for the pivot distance X which is the largest valid distance for which the cows can be accommodated. How do we know whether we can accommodate the cows for the distance X ?
We use a simple boolean check function as above which returns true if all the C cows could be fit into the N stalls with minimum distance between them being at least X. This can be simple achieved using a simple pass over the N stalls efficiently following the distance constraint and calculating the number of cows accommodated. If we are able to accommodate at least C cows, we return TRUE else we return FALSE.
TRUE denotes that this X can be a valid answer but we can also check for values greater than X. FALSE denotes that this X is invalid and we should look for values lesser than X. So we initially define the search space with the left boundary L = 0 and the right boundary R = max_possible_distance and apply binary search with the help of the check function to arrive at the final answer. The code for the whole solution can be found below.
For a similar problem, you can try the famous problem called as the Painter’s Partition Problem. The link for the problem is : https://www.interviewbit.com/problems/painters-partition-problem/
Thank You!
