有效搜索已排序的数值

Question

我有一个int[]包含具有以下属性的值的数组:

• 他们排序
• 它们是独一无二的(没有重复)
• 它们在已知范围内 [0..MAX]
• MAX通常比阵列的长度大很多(例如10-100x)
• 有时数字在整个范围内均匀分布,但在其他时候,连续数字的序列很长.我估计这两种情况之间约为50/50.

鉴于此列表,我想有效地找到数组中特定值的索引(或者如果该值不存在,则找到下一个更高的值).

我已经实现了具有间隔二分的直接二分搜索,该搜索工作得相当好,但我怀疑数据的性质/分布可以被利用来更快地收敛到解决方案.

我有兴趣优化平均案例搜索时间,但重要的是最坏的情况永远不会比O(log n)差,因为数组有时非常大.

问题:在普通情况下,有可能比纯二进制搜索做得更好吗？

编辑(澄清其他问题/评论)

• O(log n)中的常数绝对重要.事实上,假设比O(log n)更好的算法复杂度是不可能的,常量可能是唯一重要的.....
• 它通常是一次性搜索,因此虽然预处理是可能的,但它可能不值得.

Answer 1

让我们在这里命名间隔x和z搜索的数字。

由于您希望值均匀分布，因此可以使用插值搜索。这类似于二分搜索，但在 处分割索引范围start + ((z - x[start]) * (end - start)) / (x[end] - x[start])。

要获得运行时间，O(log n)您必须将插值搜索与二分搜索相结合（从二分搜索逐步执行并从插值搜索逐步执行交替执行）：

public int search(int[] values, int z) {
    int start = 0;
    int end = values.length-1;

    if (values[0] == z)
         return 0;
    else if (values[end] == z) {
        return end;
    }

    boolean interpolation = true;

    while (start < end) {
        int mid;
        if (interpolation) {
            mid = start + ((z - values[start]) * (end - start)) / (values[end] - values[start]);
        } else {
            mid = (end-start) / 2;
        }
        int v = values[mid];
        if (v == z)
            return mid;
        else if (v > z)
            end = mid;
        else
            start = mid;
        interpolation = !interpolation;
    }
    return -1;
}

由于 while 循环的每第二次迭代都会执行二分搜索中的一步，因此它最多使用二分搜索所使用的迭代次数的两倍 ( O(log n))。由于每隔一步都是插值搜索的一步，因此如果输入具有所需的属性，算法应该快速减小间隔大小。