Binary Search: Maximum and Minimum Concepts

Binary Search: Maximum and Minimum Concepts

In this blog, we will explore how binary search can be used to solve problems that involve finding the maximum or minimum value satisfying a specific condition. We'll also look at how to identify such problems, provide examples, and share a reusable template for solving them.

1. How to Identify if a Problem is a Binary Search Problem (Maximum/Minimum)

Binary search is not just limited to searching in sorted arrays. It can also be applied to problems where you need to find the maximum or minimum value that satisfies a certain condition. Here are some key indicators to identify such problems:

• Monotonic Function: The problem involves a function that is either increasing or decreasing. For example:
  • In an increasing function, For every x > y f(x) >= f(y)
  • In a decreasing function, For every x > y f(x) <= f(y)
• Search Space: The problem has a well-defined search space (e.g., a range of values) where the answer lies.
• Optimization: The problem requires finding the minimum or maximum value that meets a certain condition.

2. Example Problems

Example 1: Finding the Minimum Value (Increasing Function)

Problem: You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip. Each bus can make multiple trips successively, and all buses operate independently. You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.

Example 1:

Input: time = [1,2,3], totalTrips = 5
Output: 3
Explanation:
- At time t = 1, trips completed: [1, 0, 0]. Total trips = 1.
- At time t = 2, trips completed: [2, 1, 0]. Total trips = 3.
- At time t = 3, trips completed: [3, 1, 1]. Total trips = 5.
So, the minimum time needed is 3.

Example 2:

Input: time = [2], totalTrips = 1
Output: 2
Explanation:
There is only one bus, and it completes its first trip at t = 2.

Solution Code:

class Solution {
public:
    long long f(vector<int>& time, long long val) {
        long long a = 0;
        for (int i = 0; i < time.size(); i++) {
            a += val / time[i];
        }
        return a;
    }

    long long minimumTime(vector<int>& time, int totalTrips) {
        long long low = 1, high = 1e14;
        while (low < high) {
            long long mid = low + (high — low) / 2;
            if (f(time, mid) >= totalTrips)
                high = mid;
            else
                low = mid + 1;
        }
        return high;
    }
};

Explanation of the Code:

1. Function f:
   • This function calculates the total number of trips completed by all buses in val time.
   • For each bus, the number of trips it can complete in val time is val / time[i].
   • The function sums up the trips for all buses and returns the total.
   • Why is f increasing? As val increases, the number of trips each bus can complete also increases. Therefore, f(val) is an increasing function.
2. Binary Search Setup:
   • low = 1: The minimum possible time is 1.
   • high = 1e14: The maximum possible time is based on the constraints. Since time[i] <= 1e7 and totalTrips <= 1e7, the worst-case scenario is when there’s only one bus with time[i] = 1e7, and we need 1e7 trips. So, the maximum time required is 1e7 * 1e7 = 1e14.
3. Binary Search Logic:
   • We perform binary search on the time range [1, 1e14].
   • For each mid, we calculate the total trips using f(time, mid).
   • If f(time, mid) >= totalTrips, it means we can achieve the required trips in mid time or less. So, we update high = mid to search for a smaller time.
   • If f(time, mid) < totalTrips, we need more time, so we update low = mid + 1.
   • The loop continues until low and high converge, and we return high as the minimum time.

Example 2: Finding the Maximum Value (Decreasing Function)

Problem: Koko loves to eat bananas. There are n piles of bananas, where the ith pile has piles[i] bananas. The guards will return in h hours. Koko can decide her eating speed k (bananas per hour). Each hour, she chooses a pile and eats k bananas. If the pile has fewer than k bananas, she eats all of them and stops eating for that hour. Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation:
- At k = 4, Koko takes [1, 2, 2, 3] hours to eat each pile. Total time = 8 hours.

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Explanation:
- At k = 30, Koko takes [1, 1, 1, 1, 1] hours to eat each pile. Total time = 5 hours.

Solution Code:

class Solution {
public:
    int f(vector<int>& p, int mid) {
        int total_time = 0;
        for (int i = 0; i < p.size(); i++) {
            if (p[i] % mid == 0)
                total_time += (p[i] / mid);
            else
                total_time += (p[i] / mid) + 1;
        }
        return total_time;
    }

    int minEatingSpeed(vector<int>& p, int h) {
        int maxi = *max_element(p.begin(), p.end());
        int low = 1, high = maxi;
        while (low < high) {
            int mid = low + (high — low) / 2;
            if (f(p, mid) <= h)
                high = mid;
            else
                low = mid + 1;
        }
        return high;
    }
};

Explanation of the Code:

1. Function f:
   • This function calculates the total time required to eat all bananas at a given eating speed mid.
   • For each pile, the time taken is piles[i] / mid if divisible, otherwise (piles[i] / mid) + 1.
   • The function sums up the time for all piles and returns the total.
   • Why is f decreasing? As mid (eating speed) increases, the time taken to eat all bananas decreases. Therefore, f(mid) is a decreasing function.
2. Binary Search Setup:
   • low = 1: The minimum possible eating speed is 1.
   • high = maxi: The maximum possible eating speed is the maximum number of bananas in any pile (since eating faster than this won’t help).
3. Binary Search Logic:
   • We perform binary search on the eating speed range [1, maxi].
   • For each mid, we calculate the total time using f(p, mid).
   • If f(p, mid) <= h, it means Koko can eat all bananas within h hours at speed mid or less. So, we update high = mid to search for a smaller speed.
   • If f(p, mid) > h, Koko needs to eat faster, so we update low = mid + 1.
   • The loop continues until low and high converge, and we return high as the minimum eating speed.

3. Basic Template for Binary Search Problems for Maximum/Minimum

Here is a reusable template for solving binary search problems involving maximum or minimum values:

int/long long/bool f(....para....){
     //calculate f function value for mid;
}
int Binary_Search_For_Max_Min(....para....) {
    int low=1;
    int high=1e9; //depend on given question
    int ans=-1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (f(....mid....other Required para....)) {
            //update high/low/ans according to question
        } else {
            //update high/low/ans according to question
        }
    }
    return low/high/ans; // or high, depending on the problem
}

4. What’s Next?

In the next blog, we will dive deeper into more advanced binary search techniques, including:

• Binary search for Finding maximum/minimum value part2
• Binary search on 2D arrays or matrices.
• Binary search on Count Number of pair type problem
• Solving more complex problems that require creative applications of binary search.

Stay tuned for more insights and happy coding!