Leetcode上「Koko 吃香蕉」和 「货物运输」是通过二分搜索来确定边界的经典场景。

    • Leetcode 875

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

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

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

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

    canFinish不太好写：

    1. bool canFinish(vector<int>& piles, int speed, int Hour){
    2.      int need=0;
    3.     for(int i=0;i<piles.size();++i){
    4.          need+=(piles[i]/speed+piles[i]%speed?1:0);
    5.     }
    6.     return need<=Hour;
    7. }
    • Leetcode 1011

    **巧用二分搜索确定边界 - 图2
    要在D天内运输完所有货物，货物不可分割，最终确定运输的最小载重（下文称为cap）：
    本质上和 Koko 吃香蕉的问题一样的，首先确定cap的最小值和最大值分别为max(weights)和sum(weights)。

    1. int shipWithinDays(vector<int>& weights, int D) {
    2.     //默写出二分搜索的框架
    3.     //约定二分搜索策略为：左闭右开
    4.     int left = getMax(weights);// 载重可能的最小值
    5.     int right = getSum(weights) + 1;// 载重可能的最大值 + 1
    6.     while (left < right) {
    7.         int mid = left + (right - left) / 2;
    8.         if (canFinish(weights, D, mid)) {
    9.             right = mid;
    10.         } else {
    11.             left = mid + 1;
    12.         }
    13.     }
    14.     return left;
    15. }

    canFinish同样不太好写：

    1. bool canFinish(vector<int>& weights, int Day, int paylaod){
    2.      int i=0;
    3.     int needDay=0;
    4.     while(i!= weights.size()){
    5.          int sum=0;
    6.         while(sum+weights[i]<=payload){
    7.             sum+=weights[i];
    8.             ++i;
    9.         }
    10.         needDay++;
    11.     }
    12.     return needDay<=Day;
    13. }

    这题和画匠问题是一个意思：
    image.png
    这里画匠数量就是上一题中的Day，确定画作的最少时间就是上一题中的轮船的最小payload。