При выполнении экспоненциального поиска, почему мы выбираем основание экспоненты как 2?

Question

Можем ли мы выбрать любую базу по своему вкусу или она выбрана потому, что она обеспечивает максимальную эффективность?

Я смотрел на этот алгоритм.Что в основном дает это:

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

Помимо трудностей реализации, стоимость поиска позиции n с множителем k составляет log (n) / log (k) + log ((k-1) n) + O (1) = log (n) / log (k) + log (n) + log (k-1) + O (1). Увеличивая k, мы можем сделать подход с постоянным множителем, но не достичь 1, но стоимость - это увеличение в постоянном члене. 2 работает достаточно хорошо, я полагаю.