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

我们可以选择我们喜欢的任何一个基地，还是选择它的基地，因为它提供了最大的效率？
我在研究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？为什么没有其他号码？

最佳答案

撇开实现困难不谈，用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，而代价是常数项的增加我想两个已经足够了。

关于algorithm - 在进行指数搜索时，为什么选择指数的底数为2？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55103311/