二分查找的下界与上界

功能说明

该示例在有序数组上实现 lowerBound 与 upperBound。前者返回第一个大于等于目标值的下标，后者返回第一个大于目标值的下标。两者相减就是重复元素个数，而 lowerBound 本身可以直接作为插入位置，用于维护始终有序的列表。空数组返回 0，目标值不存在时返回的仍然是合法插入点，不会抛出越界错误。

关键代码

两个函数都使用半开区间写法，循环条件为 low < high，中点用 (low + high) >>> 1 计算，避免大下标相加后的符号问题。默认比较器按小于、等于、大于返回 -1、0、1。lowerBound 在比较结果小于 0 时移动左边界，upperBound 在小于等于 0 时移动左边界，因此重复值会被分别收束到区间两端。countOccurrences 复用两个边界，不重复扫描。

使用注意

输入数组必须已经按照同一个比较器排好序，否则返回的下标没有意义。比较器需要满足全序关系，不要在比较过程中修改数组内容。函数只返回下标，不返回元素，越界目标会得到 0 或数组长度。虽然复杂度是对数级，但每次比较都会调用自定义函数，热路径上应避免昂贵计算或副作用。

验证方式

用包含三个重复 20 的数组断言 lowerBound 为 1、upperBound 为 4、计数为 3。对不存在的 25 断言插入位置为 4。空数组的两个边界都应为 0。再用降序比较器验证边界随之反转，并传入非数组断言 TypeError，最后与 findIndex 的结果交叉比对。

代码示例

export function lowerBound(array, target, compare = defaultCompare) {
  assertArray(array);
  let low = 0;
  let high = array.length;
  while (low < high) {
    const mid = (low + high) >>> 1;
    if (compare(array[mid], target) < 0) low = mid + 1;
    else high = mid;
  }
  return low;
}

export function upperBound(array, target, compare = defaultCompare) {
  assertArray(array);
  let low = 0;
  let high = array.length;
  while (low < high) {
    const mid = (low + high) >>> 1;
    if (compare(array[mid], target) <= 0) low = mid + 1;
    else high = mid;
  }
  return high;
}

export function countOccurrences(array, target, compare) {
  return upperBound(array, target, compare) - lowerBound(array, target, compare);
}

function defaultCompare(left, right) {
  return left < right ? -1 : left > right ? 1 : 0;
}

function assertArray(array) {
  if (!Array.isArray(array)) throw new TypeError("array must be an array");
}

const scores = [10, 20, 20, 20, 35, 50];
console.log(lowerBound(scores, 20));
console.log(upperBound(scores, 20));
console.log(countOccurrences(scores, 20));
console.log(lowerBound(scores, 25));