After reading this article, you can try to solve the following problems:

875. Ke Ke who Loves bananas (Medium)

1011. Ability to deliver packages within D days (Medium)

We have made a poem before, to make sure you can write the binary search with your eyes closed. It introduces the details of binary search, discusses the “search an element”, “search the left edge”, “search the right edge” these three situations, teach you how to write a correct and 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) has been introduced, but there is no abstract out of a specific routine framework.

So this article will summarize a set of binary search algorithm using the framework routine, to help you in the binary search algorithm related to the actual problem, to think and analyze methodically, step by step, write the answer.

Warning: This article is a bit long and hardcore, and suggests learning while awake.

The original binary search code

The archetype of binary search is to search for an element target in an ordered array and return the index of that element.

If the element does not exist, what special value can be returned is a matter of fine tuning the algorithm implementation.

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 algorithm’s code.

We have discussed the above problems in detail before the binary search algorithm framework, for this is not clear readers suggest review the previous text, has been clear about the basic binary search algorithm readers can continue to see.

In specific algorithmic problems, the “search left edge” and “search right edge” scenarios are commonly used, and you are rarely asked to “search an element” alone.

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 finding the best value is necessarily the process of searching a boundary, so we will analyze the binary algorithm code of these two kinds of searching boundary in detail.

The specific code of the binary search algorithm of “search 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) {// Right = mid; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } return left; }Copy the code

Given that the input array nums = [1,2,3,3,3,5,7] and the element target = 3, the algorithm returns index 2.

If I were to draw a picture, it would look something like this:

The specific code of the binary search algorithm of “search 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) {if (nums[mid] == target) { } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } return left - 1; }Copy the code

Enter the same as above, and the algorithm returns index 4. If you draw a graph, it looks like this:

All right, so this is all review, and I think everyone who’s read this should understand. With the above image in mind, any problem that can be abstracted from the above image can be solved using binary search.

Generalization of binary search problem

What problem can we apply the binary search algorithm technique to?

First, you want to abstract an independent variable x, a function f(x) of x, and a target value from the problem.

At the same time, x, f(x) and target must satisfy the following conditions:

1. F (x) must be a monotone function on x.

2. They ask you to calculate x for the constraint f(x) == target.

The above rules may sound abstract, but here’s a concrete example:

Given an ordered array of nums in ascending order and a target element, calculate target’s index position in the array. If there are multiple target elements, return the smallest index.

This is the basic type of “search left boundary”, the solution code is written before, but what are x, f(x), target respectively?

We can consider 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]; int f(int x, int[] nums); }Copy the code

F (x) is a function that increments monotonically on x, because nums is in ascending order.

And finally, what do they want us to solve for? Shall we calculate the leftmost index of the element target?

Is it the same as asking us, “What is the minimum value of x that satisfies f(x) == target?”

Draw a picture like this:

If you have an algorithmic problem, and you can abstract it into this graph, 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; }Copy the code

This code tweaks the previous code a bit, putting a layer of function F directly accessing nums[mid], which is essentially redundant, but abstracts the idea of binary search from the framework of specific algorithmic problems.

Use binary search routine framework

If you want to use binary search to solve specific algorithmic problems, you can start with the following code framework:

// function f is a monotone function of 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 the independent variable x? int right = ... + 1; while (left < right) { int mid = left + (right - left) / 2; If (f(mid) == target) {// Ask yourself: do you want the left boundary or the right boundary? / /... } else if (f(mid) < target) {// if (f(mid) < target) { / /... } else if (f(mid) > target) {// how to make f(x) smaller? / /... } } return left; }Copy the code

Specifically, want to use binary search algorithm to solve the problem, divided into the following steps:

1, determine what x, f(x), target are respectively, and write the code for function f.

2. Find the value range of x as the search interval of binary search, initialize 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 the solution code.

Here are a few examples to illustrate the process.

Example 1: Ke Ke eats a banana

This is Question 875, “Ke Ke who loves bananas” :

Coco could eat no more than one pile of bananas an hour, and if she could not finish it, she would eat it the next hour. If you still have an appetite after the pile, you won’t eat another one until the next hour.

He wants to eat all the bananas before the guards come back, so let’s determine the minimum speed K for eating bananas. The function signature is as follows:

int minEatingSpeed(int[] piles, int H);

Copy the code

So, for this problem, how to use the summarized routine, write binary search solution code?

Think through the steps:

1, determine what x, f(x), target are respectively, and write the code for function f.

What is the independent variable x? Remember from the function graph, binary search is essentially searching for independent variables.

So whatever they want to know, let’s set as the independent variable, the rate at which Coco eats the banana is the independent variable x.

So, what is the monotone function f of x on x?

Obviously, the faster you eat a banana, the less time it takes to finish the pile, and speed and time are a monotone function.

So, the f(x) function can be defined like this:

If you eat bananas at a rate of x roots per hour, it takes f(x) hours to eat all the bananas.

The code implementation is as follows:

Int f(int[] piles, int x) {int hours = 0; // Definition: f(x) hours to eat all bananas at speed x for (int i = 0; i < piles.length; i++) { hours += piles[i] / x; if (piles[i] % x > 0) { hours++; } } return hours; }Copy the code

Target, obviously, the time limit on eating the banana H is target, 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 left and right variables.

What is the minimum rate at which Coco can eat a banana? How much is how old?

Obviously, the minimum speed should be one, and the maximum speed was the maximum number of elements in the piles, because eating a pile of bananas per hour didn’t matter.

There are two options here, either you run a for loop through the piles and calculate the maximum, or you look at the constraints given by the piles, what the range of values of the elements in the piles is, and initialize right with a value out of the range.

I chose the second option, and the problem says 1 <= piles[I] <= 10^9, so I can determine the interval boundaries for binary piles:

public int minEatingSpeed(int[] piles, int H) { int left = 1; Int right = 1000000000 + 1; / /... }Copy the code

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 speed at which the banana is eaten, f(x) is a monotonically decreasing function, and target is the time limit for eating the banana H. They want us to calculate the minimum speed, that is, x should be as small as possible:

This is a binary search for the left edge, but note that f(x) is monotonically decreasing. Do not close your eyes to the frame.

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 (haemg, mid) == H) {// To search left piles, I had to shrink right piles; } else if (f(piles, mid) < H) {right = mid; } else if (f(piles, mid) > H) {left = mid + 1; } } return left; }Copy the code

PS: As for whether mid needs + 1, the previous explanation of binary search algorithm has been analyzed in detail, which will not be expanded here.

Now that the problem is solved, we can merge the redundant if branches, and the resulting 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) decrement monotonically as X increases int f(int[] piles, int x) {// see above}Copy the code

PS: The redundant IF branches in our code framework are mainly for understanding. It is suggested to merge the redundant branches after writing the correct solution, which can improve the efficiency of algorithm operation.

Transporting goods

Let’s look at question 1011, “Ability to deliver package within D days” :

How to determine the minimum load to transport all the goods in order within D days, the goods are not divided?

The function signature is as follows:

int shipWithinDays(int[] weights, int days);

Copy the code

As in the previous problem, we just follow the process:

1, determine what x, f(x), target are respectively, and write the code for function f.

So what they’re asking us is, what is the independent variable, so the carrying capacity of the ship is the independent variable x.

The number of transport days is inversely proportional to the carrying capacity, so f(x) can be used to calculate the number of transport days required under the carrying capacity of X, and then F (x) is monotonically decreasing.

The implementation of f(x) is as follows:

Int f(int[] weights, int x) {int days = 0; for (int i = 0; i < weights.length; ) {// load as many goods as possible int cap = x; while (i < weights.length) { if (cap < weights[i]) break; else cap -= weights[i]; i++; } days++; } return days; }Copy the code

For this problem, target is obviously the transport day D, and we need to calculate the minimum load of the ship under the constraint f(x) == D.

2. Find the value range of x as the search interval of binary search, initialize left and right variables.

What is the minimum load of a ship? What is the maximum load?

The minimum weight of a boat is the maximum element in the weights array, because it has to carry at least one load at a time.

The maximum load is obviously the total of the weights array, which is to load all the items 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; for (int w : weights) { left = Math.max(left, w); right += w; } / /... }Copy the code

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 carrying capacity of the ship, f(x) is a monotonically decreasing function, target is the total number of shipping days limit D, and we are asked to calculate the minimum carrying capacity of the ship, that is, x should be as small as possible:

This is a binary search that searches the left boundary.

public int shipWithinDays(int[] weights, int days) { int left = 0; 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) { } else if (f(weights, mid) < days) {right = mid; } else if (f(weights, mid) > days) {left = mid + 1; } } return left; }Copy the code

Here, the solution to the problem is also written. Let’s merge the redundant if branches to make the code run faster. 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) {Copy the code

This article ends here, to sum up, if you find a monotonic relationship in the problem, you can try to use the idea of binary search to solve it. Figure out the types of monotony and binary search, analyze and draw, and write the final code.

View more quality algorithm articles click here, hand with your brush force buckle, committed to the algorithm to speak clearly! My algorithm tutorial has received 90K star, welcome to like!