前端知库

二分查找怎样定位时间轴边界？为什么重复值和空数组容易写错？

从视频章节和有序时间戳出发，用左闭右开区间实现 lower bound，解释循环不变量、重复值、未命中、复杂度和 JavaScript 位运算陷阱。

参考答案

简答

  • lower bound 返回第一个大于或等于目标的位置，在左闭右开区间 [lo, hi) 上二分。
  • 循环条件是 lo < hi，比较成立时 hi = mid，否则 lo = mid + 1。
  • 空数组返回 0，所有元素都小于目标时返回数组长度。
  • 有重复值时，lower bound 返回第一个匹配项，upper bound 返回最后一个之后的位置。

视频播放器保存了已排序的章节起点。用户跳到第 25 秒时，需要找到下一个章节，或者找到当前所属章节。此时搜索“是否存在 25”通常不够：即使没有恰好相等的时间，也需要返回一个边界位置。

lower bound 返回第一个大于或等于目标值的索引。如果所有值都小于目标，返回数组长度。这个约定同时覆盖插入位置、重复值的左边界和不存在相等元素的情况。

用一条不变量解释整个循环

下面约定输入为升序排列的有限数值数组，允许重复值。区间采用 [left, right)，right 初始值等于 length，不是最后一个下标。

JavaScript
function lowerBound(values, target) {
  let left = 0;
  let right = values.length;
  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);
    if (values[middle] < target) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }
  return left;
}

console.log(lowerBound([10, 20, 20, 40], 20)); // 1
console.log(lowerBound([10, 20, 20, 40], 25)); // 3
console.log(lowerBound([10, 20, 20, 40], 50)); // 4
console.log(lowerBound([], 20)); // 0

每轮循环保持：left 左边的值都小于 target，right 及其右边的值都大于或等于 target，尚未排除的候选位于两者之间。

当中点小于目标，中点也不可能是答案，所以 left 跳到 middle + 1；否则中点仍可能是第一个满足条件的位置，保留它作为新的右边界。每轮都缩小区间，直到 left 等于 right，此时边界唯一。

在 [10,20,20,40] 中查 20，第一次中点为 2，值等于目标，于是 right 变为 2。继续向左缩小，最终落在索引 1。若一遇到相等就返回，就只能找到某一个 20，无法保证是第一个。

查找下一个章节和当前章节不是同一个问题

lowerBound 可以找“不早于当前时间”的章节，但当前正在播放的章节通常需要“最后一个不大于当前时间”的起点。可以先求 upper bound，即第一个严格大于目标的位置，再减一。

JavaScript
function upperBound(values, target) {
  let left = 0;
  let right = values.length;
  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);
    if (values[middle] <= target) left = middle + 1;
    else right = middle;
  }
  return left;
}

const starts = [0, 10, 20, 40];
const current = upperBound(starts, 25) - 1;
console.log(current); // 2，对应第 20 秒开始的章节
console.log(upperBound([10, 20, 20, 40], 20) - lowerBound([10, 20, 20, 40], 20)); // 2

如果播放时间早于第一个起点，current 为 -1，调用方应显示“尚未开始”，不能直接访问数组。若下一章节索引等于 length，表示后面没有章节。两个边界相减还能得到重复值数量，不需要逐项扫描这段重复区间。

O(log n) 有前提

输入必须已经有序，并且比较规则在查询期间保持一致。算法不会自动修复乱序，遇到 NaN 时比较也不再符合预期。外部数据应在进入索引时检查类型、有限性和排序；每次查询前都扫描校验或重新排序，总成本就不再只是 O(log n)。

JavaScript 的默认 sort 按字符串比较，数值排序需要明确比较函数，例如 [...values].sort((a, b) => a - b)。不要在每次指针移动时重建排序数组；可以在数据版本变化时重建索引，然后多次查询。若搜索时数据被异步替换，结果必须与对应数据快照一起使用。

不要直接用 (left + right) >> 1 求中点。JavaScript 位运算会转为 32 位整数，大索引下可能截断或变负。Math.floor 不依赖这类 32 位转换。示例假定正常数组索引和有限数值，不是适用于任意超大 BigInt 索引的通用实现。

性能收益与业务边界

二分定位是 O(log n) 时间、O(1) 额外空间，但向普通数组中间插入仍可能移动大量元素。它只加速寻找位置，不会让更新整个结构也变成对数复杂度。小数组上直接遍历可能更简单，应结合查询频率和数据量选择。

用户输入的大数组应在入口限制容量；算法快不代表接收、复制和排序任意数据都便宜。时间戳还应统一单位，不能把毫秒数组与秒级 target 比较。音视频浮点时间是否允许误差，需要业务明确规则，不能随意在比较中加一个 epsilon 改变边界语义。

如何验证

除了几个固定输出，可以用线性扫描作为独立参照：随机生成有序数组，比较 lowerBound 与第一个满足 value >= target 的位置；未命中时使用 length。覆盖空数组、全部相等、目标小于最小值、大于最大值、负数和重复区间。再验证返回位置左侧严格小于目标、右侧大于或等于目标，这比只测一个命中例子更能发现边界错误。

本题是教学实现，参考资料用于理解二分算法和 JavaScript 数值语义，并非某个库的官方代码。

补充参考

CP-Algorithms · Binary Search反馈此题