After reading this article , You can go and get the following questions ：
1011. stay D The ability to deliver packages within days
-----------
Where can binary search be used ？
The most common example is the textbook example , stay Ordered array Search the index of a given target value in . A little bit more , If there is a repetition of the target value , The modified version of binary search can return the left or right edge index of the target value .
PS： The three binary search algorithms mentioned above are in the previous article 「 Find the details in two 」 There are code explanations , If you haven't, it's highly recommended to see .
Put aside the boring data structure of ordered array , How to apply binary search to practical algorithmic problems ？ When the search space is in order , You can do a binary search 「 prune 」, Greatly improve efficiency .
It's very mysterious , This article first uses a specific 「Koko Eat bananas 」 For example .
One 、 Problem analysis
in other words ,Koko Eat at most a bunch of bananas an hour , If you can't eat, save it for the next hour ; If you have an appetite after eating this pile , I'll only wait until the next hour to eat a pile of . Under this condition , Let's be sure Koko Banana eaters Minimum speed （ root / Hours ）.
If I give you this scenario directly , Can you think of where to use the binary search algorithm ？ If you haven't seen a similar problem , I'm afraid it's hard to relate this problem to binary search .
So let's get rid of the binary search technique , Think about how violence can solve this problem ？
PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .
First , What the algorithm requires is 「H The minimum speed of eating bananas in an hour 」, Let's call it speed, Excuse me, speed What's the biggest possibility , How much at least could it be ？
Obviously at least 1, The maximum is max(piles), Because you can only eat a bunch of bananas an hour . So the brute force solution is very simple , As long as 1 Start to exhaust to max(piles), Once it is found that a certain value can be found in H Eat all the bananas in an hour , This is the minimum speed ：
int minEatingSpeed(int[] piles, int H) {
// piles Maximum value of array
int max = getMax(piles);
for (int speed = 1; speed < max; speed++) {
// With speed Is it possible to be in H Eat bananas in hours
if (canFinish(piles, speed, H))
return speed;
}
return max;
}
Pay attention to this for loop , Is in the Continuous spatial linear search , This is the sign that binary search works . Because we're asking for a minimum speed , So you can use a Search the left boundary of binary search Instead of linear search , Improve efficiency ：
int minEatingSpeed(int[] piles, int H) {
// Apply the algorithm framework of searching the left boundary
int left = 1, right = getMax(piles) + 1;
while (left < right) {
// Prevent overflow
int mid = left + (right - left) / 2;
if (canFinish(piles, mid, H)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
PS： If you have any questions about the details of this binary search algorithm , It is suggested that we take a look at the previous article 「 Find the details in two 」 Search the algorithm template of the left boundary , It's not going to unfold here .
The rest of the auxiliary functions are also very simple , It can be disassembled step by step ：
// Time complexity O(N)
boolean canFinish(int[] piles, int speed, int H) {
int time = 0;
for (int n : piles) {
time += timeOf(n, speed);
}
return time <= H;
}
int timeOf(int n, int speed) {
return (n / speed) + ((n % speed > 0) ? 1 : 0);
}
int getMax(int[] piles) {
int max = 0;
for (int n : piles)
max = Math.max(n, max);
return max;
}
thus , With the help of binary search technique , The time complexity of the algorithm is O(NlogN).
PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .
Two 、 To extend
Allied , Let's look at another transportation problem ：
To be in D Transport all the goods within days , The goods are indivisible , How to determine the minimum load for transportation （ Hereinafter referred to as cap）？
In fact, it's essentially the same as Koko The problem with eating bananas is the same , First determine cap The minimum and maximum values of are respectively max(weights) and sum(weights).
We demand Minimum load , So we can use the binary search algorithm to optimize the linear search ：
// Find the binary search of the left boundary
int shipWithinDays(int[] weights, int D) {
// The minimum possible load
int left = getMax(weights);
// The maximum possible load + 1
int right = getSum(weights) + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(weights, D, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// If the load is cap, Is it possible to be in D The goods will be delivered within days ？
boolean canFinish(int[] w, int D, int cap) {
int i = 0;
for (int day = 0; day < D; day++) {
int maxCap = cap;
while ((maxCap -= w[i]) >= 0) {
i++;
if (i == w.length)
return true;
}
}
return false;
}
Through these two examples , Do you understand the application of binary search in practical problems ？
for (int i = 0; i < n; i++)
if (isOK(i))
return ans;
＿＿＿＿＿＿＿＿＿＿＿＿＿
my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！
