二分查找常见变种方法的代码实现-526互联

二分查找变种：

1. 查找大于target的所有值的最小索引；

2. 查找等于target的所有值的最大索引（上界）；

3. 查找大于target的所有值的最大索引；

代码示例：

/**
 * 二分查找工具对象
 */
const BinarySearch = (function() {
    return {
        /**
         * 找出大于target的所有值中的最小索引
         * @param {number[]} nums - 有序数组
         * @param {number} target - 目标值
         */
        upper(nums, target) {
            let l = 0;
            let r = nums.length;
            // 在[l, r) 范围内查找target
            while (l < r) {
                // 中位数索引
                const m = l + Math.floor((r - l) / 2);
                // 如果m位置上的值比target小或者相等，则将左指针l移动至m + 1
                if (nums[m] <= target) {
                    l = m + 1;
                }
                // 如果当前位置上的值比target大，则移动r至m
                else {
                    r = m;
                }
            }

            return l;
        },
        /**
         * 找出等于target的值的最大索引（如果没有等于target的值，则返回大于target的值中的最小索引）
         * @param {number[]} nums - 有序数组
         * @param {number} target - 目标值
         */
        ceil(nums, target) {
            // 先找出大于target元素的最小值的索引
            const upper_idx = this.upper(nums, target);
            // 如果该索引的前一个位置上的值正好等于target，返回该值
            if (upper_idx > 0 && nums[upper_idx - 1] === target) {
                return upper_idx - 1;
            }
            // 否则返回比大于target的值中的最小索引
            return upper_idx;
        },
        /**
         * 找出小于target的所有值中的最小索引
         * @param nums 
         * @param target 
         */
        lower(nums, target) {
            let l = 0;
            let r = nums.length - 1;
            // 在[l, r)范围内搜索
            while (l < r) {
                // 相对于upper函数，这里m的取值调整为“上取整”（避免l留在原地，造成死循环 ）
                const m = l + Math.ceil((r - l) / 2);
                // 当前值小于target，可能符合调整，所以将l指针调整m
                if (nums[m] < target) {
                    l = m;
                }
                // 如果大于等于target（不合符搜索目标），将r调整到m - 1
                else {
                    r = m - 1;
                }
            }

            return l;
        },
    };
})();