javascript - 使用最佳猜测修改二分搜索

Question

我正在使用非常直接的二进制搜索来返回最近元素(在下侧)的索引:

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 时间戳，并且会尽可能频繁地进行搜索。这是一个衡量瓶颈。

Answer 1

我想你在找https://en.wikipedia.org/wiki/Interpolation_search , 但我要补充一点:

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