After reading this article, you can go to the force buckle to solve the following problems:
875. Ke Ke, a Banana Eater (Medium)
1011. The ability to deliver the package within D days
I wrote a poem earlier in this article, which guarantees you can write binary search with your eyes closed. It introduces the details of binary search, discusses “search one element”, “search the left edge”, and “search the right edge”, and teaches you how to write a correct bug-free binary search algorithm.
However, the binary search code framework summarized above is only limited to the basic scenario of “searching a specified element in an ordered array”. The specific algorithm problem is not so direct, and it may be difficult for you to see that binary search can be used in this problem.
For the application of binary search algorithm in specific problems, the application of binary search (1) and the application of binary search (2) have been introduced, but there is no abstract out of a specific routine framework.
So this article will summarize a set of binary search algorithm to use the framework, to help you when you encounter binary search algorithm related to the actual problems, to be able to think and analyze methodically, step by step, write the answer.
Warning: This article is a bit longer and more hardcore. It is recommended to study while awake.
The original binary search code
The prototype of binary search is to search an element target in an “ordered array” and return the index corresponding to that element.
If the element does not exist, the details of what special value can be returned can only be solved by a fine-tuning algorithm.
There is another important problem, if the “orderly array” exist in the multiple target elements, these elements must get together, here is involved in the algorithm should be returned to the left of that target the index of the element or the most on the right side of the target element index, known as the “search” on the left side of the border and the “search” right boundary, This can also be done by tweaking the code of the algorithm.
Our previous binary search algorithm framework in detail to discuss the above issues in detail, this is not clear to the reader suggested to review the previous article, has been clear about the basic binary search algorithm readers can continue to read.
In specific algorithmic problems, the most common scenarios are “search the left edge” and “search the right edge.” Very few allow you to “search a single element.”
Because algorithm is generally allow you to get the most value, such as the use of binary search handled in (a) said in a sample to let you eat banana “minimum speed”, let you for ship “minimum capacity”, as the use of binary search (2) about the topic is more magic, let you make the sum of each subarray of minimum and maximum values “.
The process of maximizing the value is necessarily the process of searching a boundary, so we will analyze the binary algorithm code of these two search boundaries in detail.
The specific code implementation of the binary search algorithm of “searching the left boundary” is as follows:
Int left_bound(int[] nums, int target) {if (nums.length == 0) return -1; int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; If (nums[mid] == target) {if (nums[mid] == target) {right = mid; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } return left; }Assuming the input array nums = [1,2,3,3,3,5,7] and the element you want to search for is target = 3, the algorithm will return index 2.
If I were to draw a picture, it would look like this:
The specific code implementation of the binary search algorithm of “searching the right boundary” is as follows:
Int right_bound(int[] nums, int target) {if (nums.length == 0) return -1; int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; If (nums[mid] == target) {left = mid + 1; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } return left - 1; }Enter the same as above, and the algorithm will return index 4. If you draw a graph, it looks like this:
Well, all of this is review, and I think the readers who have read this far should understand. Remember the image above, and any problem that abstracts the image above can be solved using binary search.
Generalization of binary search problem
What questions can be applied to binary search algorithm techniques?
First, you abstract from the problem an independent variable x, a function of x, f(x), and a target value.
Meanwhile, x, f(x), target must meet the following conditions:
1. F (x) must be a monotonic function on x.
2. You are asked to calculate the value of x if f(x) == target.
The above rule sounds a bit abstract, but let’s take a concrete example:
Give you an ascending array nums and a target element target. Calculate the index position of target in the array. If there are more than one target element, return the smallest index.
This is the basic “search the left edge” problem, the solution code is written before, but in this x, f(x), target are what respectively?
We can think of the index of the elements in the array as the independent variable x, and the function relation f(x) can be set as follows:
Int f(int x, int[] nums) {return nums[x]; return nums[x]; }So this function, f, is actually accessing the array nums, because they gave us an array nums in ascending order, so f(x) is just monotonically increasing on x.
And finally, what did they ask us to do? Shall we calculate the leftmost index of the element target?
Is that equivalent to asking us, “What is the minimum x that satisfies f(x) == target?”
Draw a picture like this:
If you have an algorithm problem, and you can abstract it to this picture, you can apply a binary search algorithm to it.
The algorithm code is as follows:
Int f(int x, int[] nums) {return nums[x]; } int left_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; If (f(mid, nums) == target) {if (f(mid, nums) == target) { } else if (f(mid, nums) < target) { left = mid + 1; } else if (f(mid, nums) > target) { right = mid; } } return left; }This code before the code fine-tuning a bit, the direct access to NUMS [mid] set of a layer of function f, in fact, is redundant, but, this can abstract the binary search thought in the specific algorithm problem in the framework.
The framework of binary search is used
If you want to use binary search to solve specific algorithm problems, you can start from the following code framework:
// function f is a monotone function of the independent variable x int f(int x) {//... Int solution(int[] nums, int target) {if (nums. Length == 0) return -1; // Ask yourself: What is the minimum value of the independent variable x? int left = ... ; // Ask yourself: What is the maximum value of x? int right = ... + 1; while (left < right) { int mid = left + (right - left) / 2; If (f(mid) == target) {if (f(mid) == target) { / /... } else if (f(mid) < target) {// How can I make f(x) larger? / /... } else if (f(mid) > target) {// Ask yourself: How can I make f(x) smaller? / /... } } return left; }Specifically, if you want to use binary search algorithm to solve the problem, it can be divided into the following steps:
1. Determine what x, f(x) and target are respectively, and write the code of function f.
2. Find the value range of x as the search interval of binary search, initialize the left and right variables.
3, according to the requirements of the topic, determine whether to use the search left or search right binary search algorithm, write down the solution code.
Here are a few examples to illustrate this process.
Example 1: Ke Ke eats a banana
This is “Coco the Banana Eater,” on question 875:
Ke Ke could not eat more than a bunch of bananas an hour, and if she could not eat them all, she would eat them the next hour. If you still have appetite after eating one pile, you will only eat another one in the next hour.
He wants to eat all the bananas before the guards get back, so let’s determine the minimum speed K for eating the bananas. The function signature is as follows:
int minEatingSpeed(int[] piles, int H);
So, for this problem, how to use just summarized routine, write binary search solution code?
Think about it step by step:
1. Determine what x, f(x) and target are respectively, and write the code of function f.
What is our independent variable x? If you recall from the graph of the function, the essence of binary search is that you’re searching for independent variables.
So, whatever they’re asking for, they’re going to set as the independent variable, the rate at which Ke Ke eats the banana is the independent variable x.
So, what is the monotonic function f of x on x?
Obviously, the faster you eat the banana, the less time it will take to finish the whole pile, and the relationship between speed and time is a monotone function.
Thus, the function f(x) can be defined as:
If you eat bananas at a rate of x roots per hour, it will take f(x) hours to eat all the bananas.
The code is implemented as follows:
Int f(int[] piles, int x) {int hours = 0; int[] piles, int x) {int hours = 0; for (int i = 0; i < piles.length; i++) { hours += piles[i] / x; if (piles[i] % x > 0) { hours++; } } return hours; }Target is obviously the time limit for eating the banana, which is target, which is the maximum constraint on the return value of f(x).
2. Find the value range of x as the search interval of binary search, initialize the left and right variables.
What is the minimum speed at which Coco can eat a banana? How big is what?
Obviously, the minimum speed should be 1 and the maximum speed should be the maximum piles of elements in the pile, because at most you can eat a pile of bananas an hour, which is nothing to eat.
There are two options here. Either you use a for loop to traverse the piles and calculate the maximum value, or you look at the constraints they’ve given you and see what the range of the piles’ elements is and initialize the right with a value that’s outside the range.
I chose the second option and the title said 1 <= piles[I] <= 10^9, then I was able to determine the interval boundary of the binary search:
public int minEatingSpeed(int[] piles, int H) { int left = 1; Int right = 1000000000 + 1; int right = 1000000000 + 1; / /... }3, according to the requirements of the topic, determine whether to use the search left or search right binary search algorithm, write down the solution code.
Now we have determined that the independent variable x is the speed of eating the banana, f(x) is a function of monotonically decreasing, and target is the time limit of eating the banana, H. They ask us to calculate the minimum speed, that is, x should be as small as possible:
This is the binary search of the left edge of the search, but notice that f(x) is monotonically decreasing, do not close your eyes to the frame, need to think about the above, write the code:
public int minEatingSpeed(int[] piles, int H) { int left = 1; int right = 1000000000 + 1; while (left < right) { int mid = left + (right - left) / 2; If (F (Piles, Mid) == H) { } else if (f(piles, mid) < H) {// We need to give the piles of f(x) a large readlet right = mid; } else if (f(piles, piles) > H) {// Let F (piles, piles) leave = mid + 1; } } return left; }PS: Regarding whether MID needs + 1, the binary search algorithm has been analyzed in detail in the previous article, but it will not be expanded here.
With that out of the way, we can now combine the extra if branches. The final code looks like this:
public int minEatingSpeed(int[] piles, int H) { int left = 1; int right = 1000000000 + 1; while (left < right) { int mid = left + (right - left) / 2; if (f(piles, mid) <= H) { right = mid; } else { left = mid + 1; } } return left; } // F (X) Monotone decreases as X increases int F (int[] Piles, int X) {// See above}PS: The extra IF branches in our code framework are mainly for understanding. After writing the correct solution, it is suggested to merge the extra branches, which can improve the efficiency of the algorithm.
Example two, transport goods
Also look at question 1011, “Ability to deliver packages within D days” :
To transport all the goods in order within D days, the goods are indivisible, how to determine the minimum load of transport?
The function signature is as follows:
int shipWithinDays(int[] weights, int days);
As in the last problem, we can follow the process:
1. Determine what x, f(x) and target are respectively, and write the code of function f.
So what they’re asking, what they’re asking is the independent variable, which means that the capacity of the ship is the independent variable x.
The number of days of transportation is inversely proportional to the carrying capacity, so you can ask f(x) to calculate the number of days of transportation required under the carrying capacity of x, so f(x) is monotonically decreasing.
The function f(x) is implemented as follows:
Int f(int[] weights, int x) {int days = 0; int f(int[] weights, int x) {int days = 0; for (int i = 0; i < weights.length; ) Int cap = x; int cap = x; while (i < weights.length) { if (cap < weights[i]) break; else cap -= weights[i]; i++; } days++; } return days; }In this case, the target is obviously D shipping days, and we need to figure out the minimum load of the ship under the constraint of f(x) == D.
2. Find the value range of x as the search interval of binary search, initialize the left and right variables.
What is the minimum load of the ship? What is the maximum load?
The minimum weight of the ship should be the maximum value in the weights array, because at least one piece of cargo must be loaded at a time.
The maximum payload is obviously the sum of all the elements in the weights array, which means that you can load everything at once.
This determines the search interval [left, right] :
public int shipWithinDays(int[] weights, int days) { int left = 0; Int right = 1; int right = 1; int right = 1; for (int w : weights) { left = Math.max(left, w); right += w; } / /... }3, according to the requirements of the topic, determine whether to use the search left or search right binary search algorithm, write the solution code.
Now we have determined that the independent variable x is the loading capacity of the ship, f(x) is a monotonically decreasing function, and target is the limit of the total number of days of transportation D. They ask us to calculate the minimum loading capacity of the ship, that is, x should be as small as possible:
This is the binary search on the left side of the search boundary, combined with the above diagram can write binary search code:
public int shipWithinDays(int[] weights, int days) { int left = 0; Int right = 1; int right = 1; int right = 1; for (int w : weights) { left = Math.max(left, w); right += w; } while (left < right) { int mid = left + (right - left) / 2; If (f(weights, mid) == days) {// If (f(weights, mid) == days) {right = mid; } else if (f(weights, mid) < days) {return f(weights, mid) < days) {right = mid; } else if (f(weights, mid) > days) {left = mid + 1; } } return left; }Now that the solution to this problem has been written, let’s combine the extra if branches to speed up the code. The final code is as follows:
public int shipWithinDays(int[] weights, int days) { int left = 0; int right = 1; for (int w : weights) { left = Math.max(left, w); right += w; } while (left < right) { int mid = left + (right - left) / 2; if (f(weights, mid) <= days) { right = mid; } else { left = mid + 1; } } return left; } int f(int[] weights, int x) {// See above}This paper ends here. In conclusion, if the monotone relationship is found in the topic, the idea of binary search can be tried to solve it. Knowing what kind of monotony and dichotomous search are, through analysis and drawing, allows you to write the final code.
Check out more good algorithm articles
Click here to, hand in hand with you brush force buckle, committed to the algorithm to speak clearly! my
Algorithm tutorialGot 90K star, welcome thumb up!