首页 文章

最佳猜测的修改二进制搜索

提问于
浏览 次
1

我正在使用非常直接的二进制搜索来返回最近元素的索引（在下方）：

binarySearch = function(a, x) {
    var lo = -1, hi = a.length;
    while (hi - lo > 1) {
        var mid = Math.round((lo + hi)/2);
        if (a[mid] <= x) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    if (a[lo] == x) hi = lo;
    return lo;
};

它的工作原理如下：

> timestamps = [1, 3, 4, 6, 9];
> binarySearch(timestamps, 5)
2

鉴于数据的性质（视频中的时间间隔均匀），我事先已经很好地了解了当前视频时间的最近时间戳：

bestGuess = video.currentTime / video.duration * timestamps.length;

有没有办法通过开始“接近”最佳猜测来改进二进制搜索？就像是：

betterBinarySearch(timestamps, 5, bestGuess)

在某人调用过早优化之前，阵列有50-100k时间戳，并将尽可能频繁地进行搜索 . 这是一个衡量瓶颈 .

javascript algorithm

1 回答

  • 1

    我想你正在寻找https://en.wikipedia.org/wiki/Interpolation_search，但我会补充一点：

    二进制搜索保证最坏情况下的log n成本，因为每个步骤将搜索范围分为两个，但这不适用于插值搜索 . 保证体面最坏情况行为的一种方法是在插值搜索步骤和二进制搜索步骤之间交替，或者如果搜索的范围没有像预期的那样快地减少，则运行二进制搜索步骤 .

    回复于

相关问题