针对已排序的5万条时间区间数据，利用二分查找可将单次查询复杂度从o(n)降至o(log n)，再结合播放时序特性优化为局部线性扫描+回退二分，显著提升实时字幕匹配性能。
针对已排序的5万条时间区间数据，利用二分查找可将单次查询复杂度从o(n)降至o(log n)，再结合播放时序特性优化为局部线性扫描+回退二分，显著提升实时字幕匹配性能。
在实现视频字幕、弹幕触发或时间轴标注等场景中，常需根据当前播放时间（毫秒级）快速定位所属的时间区间，并返回对应消息。原始方案若每次调用 array.find() 遍历全部 50,000 条记录，最坏时间复杂度为 O(n)，每秒一次查询将带来明显延迟与CPU压力。
核心优化思路：利用数据有序性 + 查询时序局部性
✅ 前提：确保区间按 start 升序排列
若原始数据未排序，请预先执行一次排序（如 JavaScript 中 ranges.sort((a, b) => a.start - b.start)），时间复杂度 O(n log n)，仅需执行一次。
✅ 首选算法：二分查找（Binary Search）
由于区间左端点严格递增（且通常不重叠或仅轻微重叠），我们可在 O(log n) 时间内定位可能包含目标时间 t 的候选区间。注意：需验证 t ∈ [start, end]，而非仅匹配 start。
以下是 TypeScript 实现示例（兼容 JavaScript）：
function findMessageByTime(ranges: { start: number; end: number; message: string }[], time: number): string | undefined {
let left = 0;
let right = ranges.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const range = ranges[mid];
if (time >= range.start && time <= range.end) {
return range.message;
}
if (time < range.start) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return undefined; // 未命中任何区间
}⚠️ 进阶优化：播放时序感知的混合策略
视频播放具有强时间连续性（如 t=172500 → t=172501 → … → t=177000）。可维护一个“上一次命中索引”缓存，当新时间 t_new > t_prev 时，优先从 lastIndex 向后线性扫描若干项（例如 3–5 个），若未命中再对 lastIndex+1 至数组末尾执行二分查找——避免重复搜索已确定不可能包含 t_new 的前半段。
let lastIndex = 0;
function findMessageOptimized(ranges: any[], time: number): string | undefined {
// 先尝试局部前向扫描（轻量、高概率命中）
for (let i = lastIndex; i < Math.min(lastIndex + 5, ranges.length); i++) {
const r = ranges[i];
if (time >= r.start && time <= r.end) {
lastIndex = i;
return r.message;
}
if (time < r.start) break; // 后续区间 start 更大，无需继续
}
// 未命中 → 执行二分查找（限定搜索范围：lastIndex+1 到末尾）
let left = lastIndex + 1;
let right = ranges.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const r = ranges[mid];
if (time >= r.start && time <= r.end) {
lastIndex = mid;
return r.message;
}
if (time < r.start) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return undefined;
}? 关键注意事项：
- 若存在区间重叠，二分查找仍有效，但需确保逻辑能正确捕获首个/最后一个匹配项（本例默认取首个满足条件者）；
- 对于超高频查询（如每16ms一帧），建议将
ranges转为 TypedArray（如Int32Array存储 start/end）并使用 WebAssembly 加速，但5万量级下纯JS二分已足够； - 初始化时务必校验数据完整性（如
start ≤ end），避免逻辑错误； - 在 Web 环境中，可配合
requestIdleCallback或setTimeout(..., 0)异步加载/预处理，避免阻塞主线程。
综上，排序 + 二分查找是基础高效解法，叠加播放上下文感知的局部扫描策略，可在保持代码简洁的同时，将平均查询耗时稳定控制在微秒级，完美支撑实时字幕系统。
