我想在整数数组中找到第第一个整数的索引,即<= key. I can do it with binary search in log2(N)+1 compares. Shouldn't it be possible with only log2(N) compares?
// 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;
}
让我们从信息论的角度来思考这个问题。如果你有一个包含 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) 比较就足够了。
但是,如果您的元素不在集合中,则可能需要 log2(N) + 1,比较后才能意识到您已耗尽集合。最后的比较是与空集的比较,这让您意识到您已经完成了。
就我个人而言,我想知道与空集的比较是否算作比较,但我正在阅读的文本将其算作计算机将运行时间增加一步的一步。