二分搜索只能用来查找元素吗？

来源：labuladong

作者：labuladong

二分查找到底能运用在哪里？

最常见的就是教科书上的例子，在有序数组中搜索给定的某个目标值的索引。再推广一点，如果目标值存在重复，修改版的二分查找可以返回目标值的左侧边界索引或者右侧边界索引。

PS：以上提到的三种二分查找算法形式在前文 二分查找算法详解 有代码详解，如果没看过强烈建议看看。

抛开有序数组这个枯燥的数据结构，二分查找如何运用到实际的算法问题中呢？当搜索空间有序的时候，就可以通过二分搜索「剪枝」，大幅提升效率。

说起来玄乎得很，本文用「Koko 吃香蕉」和「货物运输」的问题来举个例子。

一、Koko 吃香蕉

也就是说，Koko 每小时最多吃一堆香蕉，如果吃不下的话留到下一小时再吃；如果吃完了这一堆还有胃口，也只会等到下一小时才会吃下一堆。在这个条件下，让我们确定 Koko 吃香蕉的最小速度（根/小时）。

如果直接给你这个情景，你能想到哪里能用到二分查找算法吗？如果没有见过类似的问题，恐怕是很难把这个问题和二分查找联系起来的。

那么我们先抛开二分查找技巧，想想如何暴力解决这个问题呢？

首先，算法要求的是「H小时内吃完香蕉的最小速度」，我们不妨称为speed，请问speed最大可能为多少，最少可能为多少呢？

显然最少为 1，最大为max(piles)，因为一小时最多只能吃一堆香蕉。那么暴力解法就很简单了，只要从 1 开始穷举到max(piles)，一旦发现发现某个值可以在H小时内吃完所有香蕉，这个值就是最小速度：

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 循环，就是在连续的空间线性搜索，这就是二分查找可以发挥作用的标志。

由于我们要求的是最小速度，所以可以用一个搜索左侧边界的二分查找来代替线性搜索，提升效率：

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：如果对于这个二分查找算法的细节问题有疑问，建议看下前文 二分查找算法详解 搜索左侧边界的算法模板，这里不展开了。

剩下的辅助函数也很简单，可以一步步拆解实现：

// 时间复杂度 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)。

类似刚才的问题，我们要求最小载重，可以用 for 循环从小到大遍历，那么就可以用搜索左侧边界的二分查找算法优化线性搜索：

// 寻找左侧边界的二分查找
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;
}

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

首先思考使用 for 循环暴力解决问题，观察代码是否如下形式：

for (int i = 0; i < n; i++)
    if (isOK(i))
        return answer;

如果是，那么就可以使用二分搜索优化搜索空间：如果要求最小值就是搜索左侧边界的二分，如果要求最大值就用搜索右侧边界的二分。

推荐阅读