[!info] related notes 算法面试题型 MOC 二分查找

使结果不超过阈值的最小除数

题目

1283. 使结果不超过阈值的最小除数 - 力扣（LeetCode）

题解

二分查找

题目数组由正整数组成，并保证 threshold ≥ nums.length。因此除数 max(nums) 时每项上取整为 1，一定可行；答案在 [1, max(nums)]。除数增大时上取整之和不增，找第一个使总和不超过 threshold 的值。

var smallestDivisor = function(nums, threshold) {
    function compute(ans) {
        let sum = 0;
        for (const a of nums) {
            sum += Math.ceil(a / ans);
            if (sum > threshold) return false;
        }
        return true;
    }
    
    let left = 1, right = 1;
    for (const x of nums) right = Math.max(right, x);
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (compute(mid)) {
             right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
};