⚙️ 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

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

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

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.

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){
   // ...
}

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;
        }

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

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

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;
        }

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;
}

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;
        }

✨ 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;

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! 📚