使用二分查找提高点击进度条时检索字幕索引的效率

使用二分查找提高点击进度条时检索字幕索引的效率

在现代网页应用中，点击进度条是常见的交互方式，尤其在音频播放器中，用户可以通过点击进度条快速跳转到不同的时间点。在我的英语听力训练网站项目中，我们需要根据用户点击进度条的位置，实时检索到对应的字幕内容。为了提高检索效率，我们选择使用二分查找来优化字幕索引的获取过程。

问题背景

在初始实现中，用户点击进度条后，我通过遍历字幕数组的方式来查找对应的字幕：

progress.addEventListener('click', (event) => {
    currentPlayCount = 0;
    const rect = progress.getBoundingClientRect();
    const clickX = event.clientX - rect.left;
    const width = rect.width;
    const duration = audio.duration;
    audio.currentTime = (clickX / width) * duration;
    
    // 遍历字幕查找对应时间
    for (let i = 0; i < subtitles.length; i++) {
        const startTime = parseTime(subtitles[i].start);
        const endTime = parseTime(subtitles[i].end);
        if (audio.currentTime >= startTime && audio.currentTime <= endTime) {
            currentSubtitleIndex = i;
            break;
        }
    }

    audio.play();
    startInterval();
});

这种遍历方法虽然简单，但当字幕数量较多时，性能会变差。特别是在频繁点击进度条时，性能问题变得更加显著。

解决方案：二分查找

我们可以利用字幕数组是按时间顺序排列的特点，使用二分查找来提升检索效率。二分查找的时间复杂度是 O(log n)，相比 O(n) 的遍历查找，能够大幅提高性能。

实现思路

二分查找通过不断将查找范围减半，能够快速锁定目标字幕。具体的逻辑是：

1. 比较当前时间与字幕的开始时间和结束时间。
2. 如果当前时间落在该字幕的时间范围内，则返回该字幕索引。
3. 如果当前时间小于字幕的开始时间，继续在前半部分查找；如果当前时间大于字幕的结束时间，则在后半部分查找。

二分查找代码实现

下面是我们如何在进度条点击事件中使用二分查找来优化字幕检索的代码：

progress.addEventListener('click', (event) => {
    currentPlayCount = 0;
    const rect = progress.getBoundingClientRect();
    const clickX = event.clientX - rect.left;
    const width = rect.width;
    const duration = audio.duration;
    audio.currentTime = (clickX / width) * duration;
    
    // 使用二分查找来找到当前时间对应的字幕索引
    currentSubtitleIndex = findSubtitleByTime(subtitles, audio.currentTime);

    if (currentSubtitleIndex !== -1) {
        const currentSubtitle = subtitles[currentSubtitleIndex];
        currentCaptionIndex.textContent = currentSubtitleIndex + 1;
        captions.textContent = currentSubtitle.text;
        captionsTranslation.textContent = currentSubtitle.cntext;
    }

    audio.play();
    startInterval();
});

二分查找函数

function findSubtitleByTime(subtitles, currentTime) {
    let left = 0;
    let right = subtitles.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const startTime = parseTime(subtitles[mid].start);
        const endTime = parseTime(subtitles[mid].end);

        if (currentTime >= startTime && currentTime <= endTime) {
            return mid; // 找到当前时间对应的字幕索引
        } else if (currentTime < startTime) {
            right = mid - 1; // 当前时间在前半部分
        } else {
            left = mid + 1; // 当前时间在后半部分
        }
    }

    return -1; // 未找到字幕
}

总结

使用二分查找对字幕索引进行检索，可以大幅提高字幕播放器的效率，尤其在处理大量字幕数据时。二分查找的时间复杂度为 O(log n)，相比 O(n) 的遍历查找，能够显著提升性能。如果你在项目中也遇到类似的问题，推荐尝试使用二分查找来优化你的查找逻辑。