DEV Community

Cover image for βš™οΈ Binary Search Finding Max/Min Template in Javascript
Raynaldo Sutisna
Raynaldo Sutisna

Posted on

βš™οΈ Binary Search Finding Max/Min Template in Javascript

🏁 Introduction

Albert Einstein once said, "If you can't explain it simply, you don't understand it well enough." I find great inspiration in Einstein's words, as they motivate me to explore subjects thoroughly, seeking not just surface-level knowledge but a deep understanding. When I learned about Binary Search, I thought it was just for a simple search for a specific answer. However, it is not! We can optimize the Binary Search approach with creative solving max/min questions. I was trying to figure out the easiest template to use for all scenarios.

If you don't know how the Binary Search is being used, you may go to my previous blog here.

🍌 Koko Eating Bananas

Before I explain the template, I think it's a good time to understand the problems usually look like for Binary Search Max/Min questions. Let's start to discuss the popular LeetCode question, 875. Koko Eating Bananas

Take your time to read the question before diving into my explanation. Understanding the problem is important rather than jumping to the solution directly.

If you can't figure out how to implement the Binary Search in this question, it is totally fine. I was in the same position before. Maybe you are wondering, there is no sorted number here, how could I solve with the binary search? That's a good initial thought.

At this point, I assume you already understand the problem. If not, please go back to the LeetCode, and take your time.

Understanding the Problem

The main idea of the problem is you need to find the minimum speed that could finish all the bananas less than h. Also, Koko could not eat more than a pile if the pile was less than the speed that Koko chose.

Let's take a look at the first example

Input: piles = [3,6,7,11], h = 8
Output: 4
Enter fullscreen mode Exit fullscreen mode

Start to think about how many the minimum/maximum Koko's bananas-per-hour eating that we can try to calculate.

We can assume that the maximum speed depends on the maximum number of piles of bananas. From the first example, the maximum is 11. If we pick a number greater than 11, it's just a wasteful check because there will be no difference.

3/11 = 1;
6/11 = 1;
7/11 = 1;
11/11 = 1;
Total = 4 hours

3/12 = 1;
6/12 = 1;
7/12 = 1;
11/12 = 1;
Total = 4 hours
Enter fullscreen mode Exit fullscreen mode

How about the minimum speed? We can just start from 1 because it will be the slowest speed to finish all the bananas

3/11 = 3;
6/11 = 6;
7/11 = 7;
11/11 = 11;
Total = 27 hours
Enter fullscreen mode Exit fullscreen mode

Checkpoint here. Could you see if this question is a binary search problem?

If we want to do a brute force solution, there are just doing a loop from 1 - 11 until we get the 8 hours. However, the time complexity will be O(N^2) because the calculating hours will cost another loop. This is why Binary Search is necessary.

Get A Paper and Draw!

To help you solve a binary search problem, I highly recommend that you draw on paper. It will be easier to translate the problem to your code.

Curve

After seeing the curve that we made, we can imagine how the two pointers of the binary search will move.

function minEatingSpeed(piles, h) {
    // ...
    let left number = 1;
    let right = maxPile;

    let result;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const counthours = countHour(piles, mid);

        if () {
            left = mid - 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

function countHour(piles, speed){
   // ...
}
Enter fullscreen mode Exit fullscreen mode

Take a look at the code above. I wrote the main template that we can use for Binary Search over the Solution Space problem.

Figuring out the condition

        if () {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
Enter fullscreen mode Exit fullscreen mode

Hopefully, you see this empty if statement. It's one of two things that you need to translate from the image to the code.
We should find a condition that makes the left pointer update to be mid + 1

Curve 2

        if (hours > h) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
Enter fullscreen mode Exit fullscreen mode

If you are confused, try to think h = 6, so we can pretend the minimum speed is 7 because 8 < 6. So in this condition, we need to move the left pointer to the mid + 1. On the other hand, we will move the right pointer to the mid - 1. It's also equal to hours <= h condition.

Figuring out the answer

After solving the condition for the if statement, we need to know which condition will have the result. because the condition is hours > h and it's not in the range of our answer, we can't put the result in that condition.

Return the minimum integer k such that she can eat all the bananas within h hours.

The statement above shows us that if the hours is more than h, it's the wrong answer.

        if (hours > h) {
            left = mid + 1;
        } else {
            right = mid - 1;
            result = mid;
        }
Enter fullscreen mode Exit fullscreen mode

We need to put the result = mid in the else statement. This is just my trick to easy place that line of code. I will find which statement that's include the = / equal condition. I mentioned before that the else statement is equal to hours <= h, so in that statement, we can put the code.

Final Code

You can try to run it in the LeetCode. https://leetcode.com/problems/koko-eating-bananas/

function minEatingSpeed(piles, h): number {
    const maxPile = piles.reduce((prev, curr) => Math.max(prev, curr), 0);
    let left = 1;
    let right = maxPile;

    let result = 0;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const hours = countHour(piles, mid);

        if (hours > h) {
            left = mid + 1;
        } else {
            right = mid - 1;
            result = mid;
        }
    }

    return result;
}

function countHour(piles, speed) {
    let sum = 0;
    for (const pile of piles) {
        sum += Math.ceil(pile / speed)
    }

    return sum;
}
Enter fullscreen mode Exit fullscreen mode

If you want to play around more, we can switch the condition as well. My approach starts with the left pointer movement, but if you want to start with the right pointer movement, you can use this code below. Pay attention the result also move to the first statement. Like I mentioned about my trick, it will follow whereever the condition has =.

        if (hours <= h) {
            right = mid - 1;
            result = mid;
        } else {
            left = mid + 1;
        }
Enter fullscreen mode Exit fullscreen mode

✨ Conclusion

My template works for me to understand and solve the problem with Binary Search for finding min/max. I wish this could be helpful to people who have some difficulties implementing Binary Search. I want to share this snippets again, so you can use it anytime

    let left = 1;
    let right = Math.Max; // find the lower max if it's possible

    let result = 0;
    while (left <= right) {
        if (your condition) {
            left = mid + 1; depends on your condition
            // result = mid;
        } else {
            right = mid - 1;
            // result = mid; depends on your condition
        }
    }

    return result;
Enter fullscreen mode Exit fullscreen mode

Remember there are two steps to translate the problem into the code. First one is condition, and second is the answer.

I also have another similar question to solve if you want to see your understanding after reading my blog. Try to solve this problem.
https://leetcode.com/problems/minimum-speed-to-arrive-on-time/description/

Good luck and happy reading! πŸ“š

Top comments (0)