# How to use binary search algorithm

2020-11-09 19:10:57

875. Coco, who loves bananas

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) {
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 ！