当前位置:网站首页>How to use binary search algorithm

How to use binary search algorithm

2020-11-09 19:10:57 labuladong,

After reading this article , You can go and get the following questions :

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) {
	//  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 !

版权声明
本文为[labuladong,]所创,转载请带上原文链接,感谢