algorithm - 在进行指数搜索时，为什么我们选择指数的底数为 2？

Question

我们可以选择任何我们喜欢的基地，还是选择基地是因为它提供了最大的效率？

我在看 this算法。这基本上给出了这个:

template <typename T>
int exponential_search(T arr[], int size, T key) {
    if (size == 0) {
        return NOT_FOUND;
    }

    int bound = 1;
    while (bound < size && arr[bound] < key) {
        bound *= 2;
    }


    return binary_search(arr, key, bound/2, min(bound + 1, size));
}

或 Python 等价物:

def exponential_search(arr, p):
i = 0
while (arr[2 ** i] < p):
    i += 1
binary_search(arr, p, i)

在第二个 while 循环中可以清楚地看到，它们正在设置

bound *=2

为什么是 2？为什么不是任何其他号码？

Answer 1

撇开实现困难不谈，搜索乘数为 k 的位置 n 的成本是 log(n)/log(k) + log((k-1)n) + O(1) = log(n)/log(k) + log(n) + log(k-1) + O(1)。通过增加k，我们可以使常数因子趋近但不达到1，但成本是常数项的增加。我想 2 已经足够好了。