1011. 在 D 天内送达包裹的能力(二分法)

image.png

var shipWithinDays = function(weights, D) {
    // 确定二分查找左右边界，由题干可知单个包裹不能被拆分且船的总运量一定小于等于所有货的总重，因此左右边界出现
    let left = Math.max(...weights) //所有货物中最重的那个包裹
    let right = weights.reduce((a, b) => a + b); //所有货物的总重
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        //  need 为需要运送的天数
        // cur 为当前这一天已经运送的包裹重量之和
        let need = 1, cur = 0;
        for (const weight of weights) {
            if (cur + weight > mid) {
                need++;
                cur = 0;
            } 
            cur += weight;
        }
        //以下是对二分值mid赋值给左边界还是右边界的判断，如果该次循环分组所用天数小于等于D，，我们就忽略二分的右半部分区间；当其大于 D 时，我们就忽略二分的左半部分区间。
        if (need <= D) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

个人感想：如果能确定左右边界的题目可以首先尝试二分法+判断的方式解？