二分法解决有界区间的最值问题

发表于 更新于 分类于 Waline：

最近在leetcode上遇到了几个问题都是采用二分法来解决的，总结了一下其中的规律，简单来说，如果是要从有界区间中寻找符合条件的最大值或者最小值，可以考虑采用二分法，不过不是基础的二分法，而是不断寻找左侧边界或者右侧边界的二分法。

关于寻找左侧边界或者右侧边界的二分法，可以看我之前的博客：魔鬼的二分查找

例题链接为：https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/

个人解题代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number} n
 * @param {number} index
 * @param {number} maxSum
 * @return {number}
 */
function isValid(maxNum, maxSum, leftLength, rightLength) {
    const left = Math.min(leftLength, maxNum);
    const right = Math.min(rightLength, maxNum);
    const leftMinSum = left * maxNum - left * (left - 1) / 2 + Math.max(0, leftLength - maxNum);
    const rightMinSum = right * maxNum - right * (right - 1) / 2 + Math.max(0, rightLength - maxNum);
    return leftMinSum + rightMinSum - maxNum <= maxSum;
}
var maxValue = function(n, index, maxSum) {
    let left = 0, right = maxSum;
    const leftLength = index + 1, rightLength = n - index;
    while(left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (isValid(mid, maxSum, leftLength, rightLength)) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return right >= 0 ? right : 1;
};