二分查找的标准库写法

[S-T-D]

• 寻找下边界
• 寻找上边界
• 参考资料

寻找下边界

/**
 * 寻找大于等于 target 的第一个位置
 * @param {arr} arr 数组
 * @param {number} first 开始索引（闭）
 * @param {number} last 结束索引（开）
 * @param {number} target 目标值
 * @returns {number} index arr[index] >= target
 */
function lowerBound(arr, first, last, target) {
    while (first < last) {
        const mid = first + Math.floor((last - first) / 2);
        if (arr[mid] < target) first = mid + 1;
        else last = mid;
    }
    return first;
}

这种写法遵循左闭右开的原则。

比如对于数组 const arr = [1, 3, 5, 5, 7, 9, 11]，
调用方式：lowerBound(arr, 0, arr.length, 5)，注意 last 是 arr.length，而不是 arr.length - 1。

下面看看 lowerBound 是如何执行的：

f 表示 first，l 表示 last，m 表示 mid

索引：          0   1   2   3   4   5   6   7
数组：          1   3   5   5   7   9   11

first loop:    f           m                l

second loop:   f   m       l

third loop:           f,m  l
                       
结束循环：      f === l === 2

可以看到这种写法的好处在于：

• 最后返回 first 或 last 都可以，因为它们是相等的。
• 如果答案可能不存在，那么将最后一行 return first; 改为 return arr[first] === target ? first : -1; 即可。
• 对于有重复的目标值也没关系，比如上面数组有两个 5 等于 target，因为最终得到的是一个边界索引（first 和 last），也就是说 nums[first] >= target，直接返回 first 或 last 即可。
• 可以用于求 target 在不破坏数组有序的情况下应该插入的位置，还是直接返回 first 或 last 即可。

 

寻找上边界

lowerBound 是寻找第一个大于等于 target 的位置。

upperBound 寻找的是第一个大于 target 的位置。

/**
 * 寻找大于 target 的第一个位置
 * @param {arr} arr 数组
 * @param {number} first 开始索引（闭）
 * @param {number} last 结束索引（开）
 * @param {number} target 目标值
 * @returns {number} index arr[index] > target
 */
function upperBound(arr, first, last, target) {
    while (first < last) {
        const mid = first + Math.floor((last - first) / 2);
        if (arr[mid] <= target) first = mid + 1;            // 和 lowerBound 的区别：< 变成 <=
        else last = mid;
    }
    return first;
}

 

参考资料

• 二分查找有几种写法？它们的区别是什么？ - Jason Li的回答 - 知乎
• std::lower_bound
• std::upper_bound