为什么我的二进制搜索需要额外的比较？ log2(N)+1

Question

我想在 <= 键的整数数组中找到 第一个 整数的索引。我可以在 log2(N)+1 比较中使用二进制搜索来完成。难道只有 log2(N) 比较才有可能吗？

// Returns the index of the first integer in keys <= key. size must be a power of 2.
unsigned find(int key, int* keys, unsigned size) {    
    int* origKeys = keys;

    for (int i = 0; i < log2(size); i++) {
        size /= 2;

        if (keys[size] < key)
            keys += size;
    }

    unsigned i = unsigned(keys - origKeys);
    // Not only is this step messy, because it doesn't fit the loop, but
    // now we have log2(n) + 1 comparisons.
    if (*keys < key)
        i++;

    return i;
}

Answer 1

让我们从信息论的角度来思考这个问题。如果您有一个包含 n 个元素的数组，则有 n+1 个可能的位置可以放置新元素：就在数组的任何元素之前，或者在所有元素之后。因此，您的算法需要进行足够多的比较，才能唯一地识别 n+1 个点中的哪个点是正确的。如果你没有进行足够的比较，你给出的答案并不总是正确的。

在最好的情况下，您所做的每一次比较都可以消除一半的可能位置。因此，在理论上的极限内，通过 k 次比较，你可以决定 2^k 个位置中哪个位置是正确的。由于有n+1个可能的位置，所以最坏情况下需要做lg(n+1)次比较，而不是lg n。由于您的 n 是 2 的完美幂，这意味着需要进行一次额外的比较。另一方面，如果 n 小于 2 的完美幂，那么进行 ceil(lg n) 比较就足够了。

由 Eloff 编辑，这段代码似乎按照您预测的 log2(n+1) 步给出了正确答案：

// Returns the index of the first integer in keys <= key. size must be one less than a power of 2.
unsigned find(int key, int* keys, unsigned size) {    
    int* origKeys = keys;
    size++;

    while(size > 1) {
        size /= 2;

        if (keys[size-1] < key)
            keys += size;
    }

    return unsigned(keys - origKeys);        
}

为什么我的二进制搜索需要额外的比较？ log2(N)+1

Why does my binary search need an extra comparison? log2(N)+1

c

c++

algorithm

binary-search