求适用于时间范围消息快速检索的高效算法

现有一组关联毫秒级时间范围与对应消息的字幕数据，需实现视频播放时展示对应时间区间字幕的功能。当前每秒调用array.find全量遍历查询，数据量达5万条时性能明显下降，以下是几种高效替代方案：

1. 排序+二分查找（首选方案） #

这是实现成本最低、性能提升最显著的方案，适合绝大多数字幕场景（无重叠或少量重叠区间）。

操作步骤： #

• 预处理阶段：将字幕数组按start字段升序排序，仅需执行一次，时间复杂度为O(n log n)
• 查询阶段：
  1. 用二分查找定位最后一个start小于等于当前播放时间的字幕
  2. 检查该字幕的end是否大于等于当前时间，满足则为目标字幕；若不满足，说明当前时间无匹配字幕

代码示例（JavaScript）： #

// 预处理：按start升序排序
const sortedSubtitles = originalSubtitles.sort((a, b) => a.start - b.start);

// 高效查询函数
function getCurrentSubtitle(currentTime) {
  let left = 0;
  let right = sortedSubtitles.length - 1;
  let candidate = null;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const subtitle = sortedSubtitles[mid];
    if (subtitle.start <= currentTime) {
      // 记录符合start条件的候选，继续向右寻找更晚的候选
      candidate = subtitle;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  // 验证候选的end是否覆盖当前时间
  return candidate && candidate.end >= currentTime ? candidate : null;
}

2. 时间分段索引 #

如果字幕时间分布有规律，可将时间轴划分为固定长度的分段（比如每10秒一个分段），提前将字幕归入对应的分段中，查询时仅在目标分段内遍历。

操作步骤： #

• 预处理阶段：
  1. 确定时间轴的最大范围，设置分段间隔（如10000ms）
  2. 遍历所有字幕，将其加入start所在的分段；若字幕跨多个分段，需加入所有覆盖的分段
• 查询阶段：
  1. 计算当前时间所属的分段key
  2. 在该分段的字幕列表中查找匹配项（可结合二分进一步优化）

优势： #

分段后每个分组的数据量远小于原数组，查询时的遍历范围大幅缩小，适合数据量极大的场景。

3. 线段树（复杂场景适用） #

如果存在大量重叠字幕（需同时展示多条消息），线段树是更适合的选择，可将区间查询的时间复杂度降至O(log n + k)（k为匹配的字幕数量）。

核心逻辑： #

• 预处理阶段：构建线段树，将每个字幕的时间区间插入对应节点
• 查询阶段：查询当前时间点对应的所有覆盖区间，返回所有匹配的字幕

适用场景： #

需要同时展示多条重叠字幕的复杂需求，实现成本略高，但能应对极端复杂的区间查询场景。

注意事项： #

• 所有预处理操作仅需执行一次，后续查询均为高性能操作
• 若字幕数据动态更新，需实现增量更新逻辑，避免全量重新预处理

内容的提问来源于stack exchange，提问作者user9987656