3-5.4 example of binary search algorithm

5.3 how to apply binary search algorithm

5.3.1 problem analysis

When binary search is applied to practical algorithm problems, it usually has a feature that the search space is ordered.

Ke Ke likes bananas. There are n piles of bananas, and there are piles[i] bananas in pile I. The guards have left and will be back in h hours.

Ke Ke can determine the speed K (unit: root / hour) at which she eats bananas. Every hour, she will choose a bunch of bananas and eat K of them. If the pile of bananas is less than k, she will eat all the bananas in the pile, and then she will not eat more bananas in this hour.

Ke Ke likes to eat slowly, but still wants to eat all the bananas before the guards come back.

Returns the minimum speed K at which she can eat all bananas in h hours (k is an integer).

Source: LeetCode
Link: https://leetcode.cn/problems/koko-eating-bananas
The copyright belongs to Lingkou network. For commercial reproduction, please contact the official authorization. For non-commercial reproduction, please indicate the source.

That is to say, input a positive integer array of length N, where piles represents n piles of bananas, and piles[i] the number of bananas in the ith pile. Now koko needs to eat these bananas within H hours
Koko eats bananas at a rate of k per hour, and he can eat a bunch of bananas at most every hour. If he can't eat them, he can save them for the next hour. If he has an appetite after eating them, he will only wait until the next hour to eat them
Under this condition, please write an algorithm to calculate that Koko needs to eat at least a few bananas per hour to eat them in H hours?
The algorithm requires the minimum rate of eating bananas within H hours. It is advisable to set Koko's rate of eating bananas as speed. What is the maximum possible speed? At least how much is possible?

At least: it will be at least 1, because it is impossible to eat bananas if it is 0

At most: max(piles) at most, because you can only eat a bunch of bananas at most in an hour

5.3.2 code implementation

Violent solution: enumerate from 1 to max(piles). Once a certain value is found, all bananas can be eaten within H hours. This is the minimum speed

    public int minEatingSpeed(int[] piles, int h) {
        int max = piles[getMaxIndex(piles)];
        int speed;
        for(speed = 1;speed<=max;speed++){
            if(canFinish(piles,speed,h)){
                break;
            }
        }
        return speed;
    }

Observe this for loop, which is characterized by linear search in continuous space, which is the sign that binary search can play a role. Since the minimum speed is required, a binary search for the left boundary can be used instead of linear search

    public int minEatingSpeed(int[] piles, int h) {
        int left =1,right=piles[getMaxIndex(piles)]+1;//Define the search interval [left, right], right unreachable
        while (left < right){
            int mid = left + (right-left)/2;
            if(canFinish(piles,mid,h)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }

Let's review why we can search for the left boundary in this way
- First, our search interval is [left, right], and then when we want to find the left boundary, the processing is as follows: when we find a reasonable target, we will approach right to the left and keep shrinking to the left, so as to obtain the effect of locking the left boundary

    public int minEatingSpeed(int[] piles, int h) {
        int left =1,right=piles[getMaxIndex(piles)]+1;//Define the search interval [left, right], right unreachable
        while (left < right){
            int mid = left + (right-left)/2;
            if(canFinish(piles,mid,h)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
    //O(N)
    private boolean canFinish(int[] piles,int speed,int h){
        int time = 0;
        for (int pile : piles) {
            time += timeOf(pile,speed);
            if(time>h){
                return false;
            }
        }
        return time<=h;
    }
    //How long will it take to eat bananas at speed?
    private int timeOf(int n,int speed){
        //If n > speed, the integer is rounded up. For example, my n is 5 and speed is 2. It takes 3 hours
        //If n < speed, it only takes one hour
        return (n/speed)+((n%speed>0)?1:0);
    }
    private int getMaxIndex(int[] piles){
        int idx=0,max=Integer.MIN_VALUE;
        for(int i = 0;i<piles.length;i++){
            if(max<piles[i]){
                max = piles[i];
                idx = i;
            }
        }
        return idx;
    }

5.3.3 extension

Packages on the conveyor belt must be transported from one port to another within days.

The weight of the ith package on the conveyor belt is weights[i]. Every day, we load packages onto the conveyor belt in the order of given weights. We will not load more than the maximum carrying capacity of the ship.

Return the minimum carrying capacity of the ship that can deliver all packages on the conveyor belt within days.

Source: LeetCode
Link: https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days
The copyright belongs to Lingkou network. For commercial reproduction, please contact the official authorization. For non-commercial reproduction, please indicate the source.

This question is similar to the previous one. Give you a positive integer array weights and a positive integer D, where weights represents a series of goods, and the value of weights[i] represents the weight of the i-th article. The goods are inseparable and must be installed and transported in sequence. Please calculate the minimum carrying capacity of the cargo ship that can carry all the goods in D days
Our question is the same as the previous one. Let's analyze it first. What is the maximum carrying weight? At least how much?

At least: max(weights), because once it is less than this value, it is impossible to complete the shipment

At most: sum(weights), which can be shipped in one day

The minimum load is required, so the linear search can be optimized by the dichotomous search algorithm that searches the left boundary

    public int shipWithinDays(int[] weights, int days) {
        int[] maxAndSum = getMaxAndSum(weights);
        int left = maxAndSum[0],right = maxAndSum[1]+1;
        //Define the search interval [left, right], right unreachable
        while (left<right){
            int mid = left + (right-left)/2;
            if(canFinish(weights,days,mid)){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
    private int[] getMaxAndSum(int[] weights){
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int weight : weights) {
            max = Math.max(max,weight);
            sum += weight;
        }
        int[] ans = new int[2];ans[0] = max;ans[1]=sum;
        return ans;
    }
    //If the load is cap, can the goods be transported within D days
    private boolean canFinish(int[] weights,int days,int cap){
        int i = 0;
        for(int day = 0 ;day<days;day++){
            //Initialization load
            int maxCap = cap;//Indicates the carrying capacity of the day, and then starts loading
            while ((maxCap -= weights[i]) >= 0){//Keep loading. Once it is less than, it means that the carrying capacity of the day has reached the limit and cannot be loaded again
                i++;
                if(i == weights.length){
                    return true;
                }
            }
        }
        return false;
    }

5.4 how to solve the problem of receiving rainwater efficiently

5.4.1 problem description

Given n non negative integers to represent the height map of each column with a width of 1, calculate how much rain can be received by the columns arranged according to this.

[external link image transfer failed. The source station may have anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-foli2yst-1661782052076) (. / image / JYS. PNG)]

Input a nums array with a length of n to represent a row of columns with a width of 1 in the two-dimensional plane. Each element nums[i] is a non negative frame number and represents the height of the ith column. Now, please calculate how much rain these columns can hold if it rains?

5.4.2 core ideas

When we find that this problem is completely out of our mind, it is usually because we look at the problem from the perspective of the whole, resulting in the complexity of the problem being amplified. At this time, we may as well consider only the part and start with the part, just like handling strings, not how to handle the whole string, but how to handle each character
We thought it was difficult before because we saw the whole array. Now we start from a single element and analyze it with i=4 of the title. How much water can be filled when i=4? It's easy to find it at this time. It can hold two pieces of water
How did you get these two waters? Looking from i=4 to the left, the height of the highest column on the left is 2, looking to the right, the height of the highest column on the right is 3, and the smaller one is taken as the limit. Then the corresponding column height of i=4 is 0, so 2-0 is two water

The above process is represented by code

water[i] = Math.min(
	//The highest pillar on the left
    Math.max(height[0...i])
    //The highest pillar on the right
    Math.max(height[i...n-1])
) - height[i]

Violent algorithm

    public int trap(int[] height) {
        int n = height.length;
        int ans = 0;
        for(int i = 1;i<n-1;i++){
            int lMax = 0,rMax = 0;
            //Look for the highest pillar on the right
            for(int j = i;j<n;j++){
                rMax = Math.max(rMax,height[j]);
            }
            //Look for the highest pillar on the left
            for(int j = i;j>=0;j--){
                lMax = Math.max(lMax,height[j]);
            }
            //Calculate the water that can be filled
            ans += Math.min(lMax,rMax) - height[i];
        }
        return ans;
    }

5.4.3 memo optimization

In the previous solution, the maximum value between height[0...i] is calculated every time, and it is solved by loop traversal. But if we know height[0...i-1], will we be able to know height[0...i] by comparing it with height[i]
Idea: create two arrays rMax and lMax as memos, where the definition is: lMax[i] represents the height of the highest column in height[0...i], rMax[i] represents the height of the highest column in height[i...n-1]. Note that base case, lMax [0] = height [0], rMax [n-1] = height [n-1]

    public int trap(int[] height) {
        if(height.length == 0){
            return 0;
        }
        int n = height.length;
        int ans = 0;
        int[] lMax = new int[n];lMax[0] = height[0];
        int[] rMax = new int[n];rMax[n-1] = height[n-1];
        //Calculate lMax from left to right
        for(int i =1;i<n;i++){
            lMax[i] = Math.max(height[i],lMax[i-1]);
        }
        //Calculate rMax from right to left
        for(int j = n-2;j>=0;j--){
            rMax[j] = Math.max(height[j],rMax[j+1]);
        }
        //Calculate the answer
        for(int i =1;i<n-1;i++){
            ans += Math.min(lMax[i],rMax[i])-height[i];
        }
        return ans;
    }

5.4.4 double pointer solution

The idea of this solution is completely consistent with the previous one, but the implementation method is very ingenious. The main difference is that the memo is pre processed in advance, while the double pointer is calculated while walking, which saves space complexity

Core code

    public int trap(int[] height) {
        if(height.length == 0){
            return 0;
        }
        int n = height.length;
        int ans = 0;
        int left = 0;
        int right =n-1;
        int lMax = height[0];//lMax is the height of the highest column in height[0...left]
        int rMax=height[n-1];//rMax is the height of the highest column of height[right...n-1]
        while (left<=right){
            lMax = Math.max(lMax,height[left]);
            rMax = Math.max(rMax,height[right]);
            //ans += Math.min(lMax,rMax)-height[i]
            if(lMax < rMax){
                ans += lMax- height[left];
                left++;
            }else{
                ans += rMax - height[right];
                right--;
            }
        }
        return ans;
    }

Solution analysis

Reviewing the previous memo solution, lMax[i] and rMax[i] represent the height of the highest column of height[0...i] and height[i...n-1]

In this double pointer solution, lMax and rMax represent the height of the highest column of height[0...left] and height[right...n-1]

At this time, lMax must be the column with the highest coordinate of the left pointer, but rMax is not necessarily the highest column on the right of the left pointer (according to the definition)

We only care about min(lMax,rMax). Let's think about what kind of situation can ensure that the water we get is right

We know that for the left pointer, the lMax on the left must be the highest column on the left of height[left]. If we want to determine the storage of this grid of water, we must know the highest height of the corresponding column on the right. At this time, there are two cases

[1] At this time, the highest height of the column corresponding to the right generated by the traversal is higher than the highest height on the left. At this time, it can be determined that only Lmax height [left] can be installed

Height of high column