koko偷香蕉

|

如何运用二分查找算法

二分查找到底有能运用在哪里？
最常见的就是教科书上的例子，在有序数组中搜索给定的某个目标值的索引。再推广一点，如果目标值存在重复，修改版的二分查找可以返回目标值的左侧边界索引或者右侧边界索引。
PS：以上提到的三种二分查找算法形式在前文「二分查找详解」有代码详解，如果没看过强烈建议看看。
抛开有序数组这个枯燥的数据结构，二分查找如何运用到实际的算法问题中呢？当搜索空间有序的时候，就可以通过二分搜索「剪枝」，大幅提升效率。
说起来玄乎得很，本文先用一个具体的「Koko 吃香蕉」的问题来举个例子。

一、问题分析


也就是说，Koko 每小时最多吃一堆香蕉，如果吃不下的话留到下一小时再吃；如果吃完了这一堆还有胃口，也只会等到下一小时才会吃下一堆。在这个条件下，让我们确定 Koko 吃香蕉的最小速度（根/小时）。
如果直接给你这个情景，你能想到哪里能用到二分查找算法吗？如果没有见过类似的问题，恐怕是很难把这个问题和二分查找联系起来的。
那么我们先抛开二分查找技巧，想想如何暴力解决这个问题呢？
首先，算法要求的是「H 小时内吃完香蕉的最小速度」，我们不妨称为 speed，请问 speed 最大可能为多少，最少可能为多少呢？
显然最少为 1，最大为 max(piles)，因为一小时最多只能吃一堆香蕉。那么暴力解法就很简单了，只要从 1 开始穷举到 max(piles)，一旦发现发现某个值可以在 H 小时内吃完所有香蕉，这个值就是最小速度：

1
2
3
4
5
6
7
8
9
10
int minEatingSpeed(int[] piles, int H) {
	// piles 数组的最大值
    int max = getMax(piles);
    for (int speed = 1; speed < max; speed++) {
    	// 以 speed 是否能在 H 小时内吃完香蕉
        if (canFinish(piles, speed, H))
            return speed;
    }
    return max;
}

注意这个 for 循环，就是在连续的空间线性搜索，这就是二分查找可以发挥作用的标志。由于我们要求的是最小速度，所以可以用一个搜索左侧边界的二分查找来代替线性搜索，提升效率：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int minEatingSpeed(int[] piles, int H) {
    // 套用搜索左侧边界的算法框架
    int left = 1, right = getMax(piles) + 1;
    while (left < right) {
        // 防止溢出
        int mid = left + (right - left) / 2;
        if (canFinish(piles, mid, H)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

PS：如果对于这个二分查找算法的细节问题有疑问，建议看下前文「二分查找详解」搜索左侧边界的算法模板，这里不展开了。
剩下的辅助函数也很简单，可以一步步拆解实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 时间复杂度 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;
}

至此，借助二分查找技巧，算法的时间复杂度为 O(NlogN)。

二、扩展延伸

类似的，再看一道运输问题：

要在 D 天内运输完所有货物，货物不可分割，如何确定运输的最小载重呢（下文称为 cap）？
其实本质上和 Koko 吃香蕉的问题一样的，首先确定 cap 的最小值和最大值分别为 max(weights) 和 sum(weights)。
我们要求最小载重，所以可以用搜索左侧边界的二分查找算法优化线性搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 寻找左侧边界的二分查找
int shipWithinDays(int[] weights, int D) {
	// 载重可能的最小值
    int left = getMax(weights);
	// 载重可能的最大值 + 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;
}
// 如果载重为 cap，是否能在 D 天内运完货物？
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;
}

通过这两个例子，你是否明白了二分查找在实际问题中的应用？

1
2
3
for (int i = 0; i < n; i++)
    if (isOK(i))
        return ans;

上一篇：如何计算编辑距离
下一篇：如何高效解决接雨水问题
目录