Binary Search on Answer

This blog is a sequel to the blog https://hashnode.com/post/clz7xrmbw000j08l2ckev8a3x which explains the basic intuition, understanding and usage of binary search algorithm. This blog teaches the application of binary search in solving problems.

Solving problems using binary search.

Binary search can't be just used to solve "find the number in sorted array" problems. It can be used to solve problems which can seem very hard to solve with their given constraints. Binary Search on Answer is one of these methods to approach hard problems.

I generally look out for these keywords: max, min, max of min, min of max in the question. There keywords increase the possibility that the question could be solved using binary search algorithm. IT IS NOT NECESSARY in every case that binary search would work, but we sort of get a hint from these keywords that we can try to use binary search.

These keywords represent just a subset of the problems that can be solved using binary search, it is not limited to max or min problems only. So in case a different question without max/min keywords comes up, you should not reject the possibility that binary search can't be used.

Basic Approach

Lets take the example of finding square root of a number with decent precision. You are given the number X. You apply binary search on the answer.

Applying binary search on the answer means that you will try to SEARCH THE ANSWER DIRECTLY.

Decide the [low, high] upper and lower limits for your answer. Suppose X <= 1e18. Now your upper and lower limits can be [0, 1e9] because the answer won't go out of this range.

Now we will keep checking the middle value if it could be the answer. To check the middle value, we will have to make a function which maps the search space to true and false. This is also called the PREDICATE FUNCTION.

We can keep checking to the RIGHT if our current answer if SMALL, and keep checking to the LEFT when our current answer is GREATER OR EQUAL.

How do we handle the decimal precision ?

Handling decimal precision

Since the computer has limited space to store any number in a variable, thus it also has limited precision for the digits after . (decimal).

Square roots can be irrational, and they can have a non terminating decimal expansion. We can constrain the accuracy until a certain limit. That means we could set a minimum precision and check the result on the basis of that.

We can set something like this | answer*answer - x | <= eps where eps is the precision. eps = 0.0000001 is a possible value. Now the value of eps we put depends on how much precise we want our answer to be.

Its my general recommendation to use eps = 1e-7 or 1e-8. If you try to use smaller eps there could be some issues with the algorithm, which I will discuss in the end.

Code

double sqroot(double x) 
{
    // the lower and upper limits
    double low = 0;
    double high = x;
    double mid = (low+high) / 2;

    // Set the precision.
    const double eps = 0.0000001;

    // Keep doing binary search until the answer is precise enough.
    while(abs(mid*mid - x) >= eps) {
        mid = (low + high)/2;

        // Reduce the search space accordingly.
        if(mid*mid < x) {
            low = mid;
        } else {
            high = mid;
        }
    }

    return mid;
}

Bug in the code

While using the above mentioned method of implementation, there is a bug in that could occur in the code which can send it into an infinite loop ( the occurrence of the bug depends on the input ).

As I already mentioned that the precision in computers is limited, i.e. the computer can only store a fixed amount of numbers after decimal. Now consider the following case:

ASSUME that a computer can store only 10 decimal digits of precision. I have stored the number 38238844.51 and 38238844.52. These are my low and high.

If I find the mid of these elements : mid = (low + high)/2
mid = (38238844.51 + 38238844.52) / 2 = 38238844.515
But our computer stores it as 38238844.51 which is equal to low itself, since our computer can store only 10 significant digits.
Now this portion of the code becomes an infinite loop. Can you see why ?

        // mid = low again in every iteration.
        // thus the loop can't progress furthur
        // search space remains [low, high], it does not reduce
        mid = (low + high)/2;
        if(mid*mid < x) {
            low = mid;
        } else {
            high = mid;
        }

We can try a smart technique to solve this problem. We know that at maximum the numbers can lie in the range [0, 10^18] in c++ (long long datatype). To find the closest integer square root, we need at most log(10^18) ~ 60 iterations. Then until 10 max digits of precision after decimal point (if possible) we would require log(10^(18 + 10)) < 100 iterations. If you can't understand the math, then you can just understand that within 100 iterations of the while loop, you will get sufficient precision.

So we modify the code as follows:-


    int maxIteration = 100;    
    while(maxIteration-- > 0) {
        mid = (low + high)/2;
        // Reduce the search space accordingly.
        if(mid*mid < x) {
            low = mid;
        } else {
            high = mid;
        }
    }

This code is bug free now. The loop will surely halt after 100 iterations.

Question 2 - Koko Eating Bananas

Question Link: https://leetcode.com/problems/koko-eating-bananas/description/

Koko loves to eat bananas. There are n piles of bananas, the i th pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integerksuch that she can eat all the bananas withinhhours.

Try it yourself first before looking at the solution.
Hint: apply the binary search on answer.

Solution of Question 2

The problem is a minimization problem. Thus we get the hint that we can try to apply binary search to this.

We need to return the minimum k. So we apply the binary search on k. If k is a big number, by the general understanding of the question, koko could eat the bananas in less than h hours ( Suppose h = 5, and piles = [1, 2, 1] and k = 100, so he takes 3 hours ).

If k is small, its not possible to eat in less than h hours. So our search space is something like F F F F F F T T T T T T for the values of k ranging from small to large. Since there will be a minimum value of k for which he can eat the bananas in less than h hours.
And we need to find the first T (leftmost T).

So we decide the upper and lower limits of our answer. Upper limit could be the maximum value of any piles[i] (10^9). Lower limit could be 1, since piles[i] > 0.

Search space for k : [ 1, 10^9 ]

There is also a constraint on h. piles.size() <= h <= 10^9. So the answer will always exist for the problem's input, because we can just choose k = maximum value of piles[i] and koko can eat all the piles within h hours. Although I'll provide a code which will also take care of the case when h < piles.size() (Answer doesn't exist).

NOTE: Since number of bananas = piles.size() * max( piles[i] ) <= 10^13 according to the constraints in the problem, therefore the number of hours can also reach this value (The case when k = 1). Therefore be careful of the overflow and use long long datatype.

class Solution {
private:
    // Calculate the number of hours taken to eat all the bananas
    // if you can eat at maximum k bananas in 1 hour from 1 pile.
    long long hoursTakenToEat(vector<int>& piles, int k) {

        // Take care of integer overflows.
        long long hours = 0;
        for(int& bananaCount : piles) {
            hours += ceil(bananaCount/(k*1.0));
        }
        return hours;
    }
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int low = 1;
        int high = 1e9;
        int mid;

        // Default value of ans in case its impossible to find answer.
        int ans = -1;

        while(low <= high)
        {
            mid = low + (high - low)/2;
            if(hoursTakenToEat(piles, mid) > h) {
                low = mid + 1;
            } else {
                ans = mid;
                high = mid - 1;
            }
        }

        if(ans == -1) {
            // Handle the case when its impossible for koko to eat
            // the bananas in h hours.
        }

        return ans;
    }
};

Binary Search on Answer - perfect_1

Table of contents

Solving problems using binary search.

Basic Approach

Handling decimal precision

Code

Bug in the code

Question 2 - Koko Eating Bananas

Solution of Question 2

Practice Questions

Blog by

Subscribe to my newsletter

Dhruv Chouhan

Dhruv Chouhan