Dichotomy Method for Solving the Optimum Problem of Bounded Interval

Recently, I encountered several problems on leetcode that were solved by dichotomy. I summarized the rules. To put it simply, if you want to find the maximum or minimum value that meets the conditions from a bounded interval, you can Consider using a dichotomy, but it is not the basic dichotomy, but a dichotomy that keeps looking for the left boundary or the right boundary.

For the dichotomy of finding the left boundary or the right boundary, see my previous blog:魔鬼的二分查找

The link to the example is: https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/

The personal problem-solving code is:

/**
 * @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;
};