二分查找-以包裹速度问题为例

二分搜索的关键在于target、目标单调，故关键点为target、x、f(x)

故二分搜索常用于速度/能力界限问题，如每天吃几个香蕉/运多少货物

其中mid=left+(right-left)/2优于mid=(left+right)\2是因为：对于大数，相加可能溢出

左闭右开区间中，左右相等是没有意义的，所以循环中的限制条件应该是left<right

左闭右开区间最后找到的边界的值在left，找到的确值在mid，这是因为，找到对应相等时，对left的值是确界（已被更新或在equal else中被更新）

（为什么mid不是确界？因为mid只是相等，没有界限意义）

而mid的值立即与target相关（equal else直接判断），若在equal else中更新left=mid，也可返回确值left

二分思维的精髓就是：通过已知信息尽可能多地收缩（折半）搜索空间，从而增加穷举效率，快速找到目标。

/**
 * 这题的x为运载能力，f(x)为运载天数，target为days
 * 因为不能拆分，运载能力至少要保证最大物品能一天送达，至多为送达所有物品，然后对于运载的包裹数组，对于运载能力进行二分查找，
 * 将运载天数与days比较，找到满足天数小于等于days的最小运载能力
 */
class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 1, middle, min = Integer.MAX_VALUE;// 定义运载数量的范围,左闭右开故right初值不为0为1
        for (int i = 0; i < weights.length; i++) {
            left = Math.max(weights[i], left);
            right += weights[i];
        }
        while (left < right) {
            middle = left + (right - left) / 2;
            if (f(weights, middle) <= days) {
                min = Math.min(middle, min);
                right = middle;
            } else
                left = middle + 1;
        }
        return min;
    }

    int f(int[] weights, int x) {// 计算运载天数
        int days = 0, cap = 0;// capability
        for (int i = 0; i < weights.length;) // i代表货物下标,运到把货运完为止
        {
            cap = x;// 可运载量-初值为x
            while (i < weights.length)// 同样，此处运到把货运完为止，且运到货才会继续
            {
                if (cap < weights[i])
                    break;
                cap -= weights[i];
                i++;
            }
            days++;
        }
        return days;
    }
}