Найти индекс k элемента x в массиве в O (log (k)) time

Question

Изучение теста и обнаружение этой проблемы, с которой мне бы хотелось помочь.

Проблема:

Пусть A = (a_1, a_2, ..., a_n) быть отсортированный массив п различных элементов и х элемент в А.

Design уплотнительное (logk) -time алгоритм для вычисления индекса k ячейки A, содержащего x (то есть A [k] = x).

Обратите внимание, что если k = theta (n), то будет выполняться стандартный бинарный поиск. Однако k может быть намного меньше n.

Answer 1

1. Давайте проверим элементы a[1], a[2], a[4], ... и так далее (индексы являются степенями 2), пока мы тот, который больше или равно х. Для этого шага требуются операции O(log k) (потому что мы останавливаемся, когда находим первую мощность двух, которая больше или равна k, которая не более 2^(log(k) + 1)).

2. Теперь у нас есть диапазон, который содержит не более 2 * k - 1 элементов. Таким образом, мы можем применять стандартный бинарный поиск. Для этого требуются операции O(log (2 * k - 1)) = O(log k).

Таким образом, общая сложность времени O(log k).