# How to use Binary Search

**Translator: ****Dong Wang**

**Author: ****labuladong**

In what scenarios can binary search be used？

The most common example is in textbook, that is, searching for the index of a given target value in **an ordered array**. Moreover, if the target values is duplicated, the modified binary search can return the left boundary or right boundary index of the target value.

PS: The three binary search algorithms mentioned above are explained in detail in the previous Binary Search Detailed Explanation. It is strongly recommended if you haven't read it.

Putting aside the boring ordered array, how can binary search be applied to practical algorithm problems? When the search space is in order, you can perform *pruning* through binary search, greatly improving efficiency.

Talk is cheap, show you the specific *Koko eating banana* problem.

## 1. Problem analysis

Koko loves to eat bananas. There are `N`

piles of bananas, the `i`

-th pile has `piles[i]`

bananas. The guards have gone and will come back in `H`

hours.

Koko can decide her bananas-per-hour eating speed of `K`

. Each hour, she chooses some pile of bananas, and eats `K`

bananas from that pile. If the pile has less than `K`

bananas, she eats all of them instead, and won't eat any more bananas during this hour.

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

Return the minimum integer `K`

such that she can eat all the bananas within `H`

hours.

**Example 1:**

**Example 2:**

In other words, Koko eats up to a bunch of bananas every hour. 1. If she can't, she can eat them until the next hour. 2. If she has an appetite after eating this bunch, she will only eat the next bunch until the next hour.

Under this condition, let us determine **the minimum speed** Koko eats bananas.

Given this scenario directly, can you think of where you can use the binary search algorithm? If you haven't seen a similar problem, it's hard to associate this problem with binary search.

So let's put aside the binary search algorithm and think about how to solve the problem violently?

First of all, the algorithm requires *minimum speed of eating bananas in **H** hours*. We might as well call it `speed`

. What is the maximum possible `speed`

? What is the minimum possible `speed`

?

Obviously the minimum is 1 and the maximum is `max(piles)`

, because you can only eat a bunch of bananas in an hour. Then the brute force solution is very simple. As long as it starts from 1 and exhausts to `max(piles)`

, once it is found that a certain value can eat all bananas in `H`

hours, this value is the minimum speed.

Note that this for loop is a linear search in **continuous space, which is the flag that binary search can work**. Because we require the minimum speed, we can use a **binary search algorithm to find out the left boundary** to replace the linear search to improve efficiency.

PS: If you have questions about the details of this binary search algorithm, it is recommended to look at the algorithm template on the left boundary of the search for Binary Search Detailed Explanation in the previous article.

The remaining helper functions are also very simple and can be disassembled step by step.

So far, with the help of the binary search, the time complexity of the algorithm is O(NlogN).

## 2. Extension

Similarly, look at a transportation problem again.

The `i`

-th package on the conveyor belt has a weight of `weights[i]`

. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within `D`

days.

**Example 1:**

To transport all the goods within `D`

days, the goods are inseparable. How to determine the minimum load for transportation(hereinafter referred to as `cap`

)?

In fact, it is essentially the same problem as Koko eating bananas. First, determine the minimum and maximum values of `cap`

as `max(weights)`

and `sum(weights)`

.

We require **minimum load**, so a binary search algorithm that searches the left boundary can be used to optimize the linear search.

Through these two examples, do you understand the application of binary search in practical problems？

Last updated