Учитывая упорядоченный массив A[1...n] ключей, а другой ключ, x, хранящийся в A, показать, как найти индекс, k, так что A[k] = x во время O(log(k)).Поиска индекса в отсортированном массиве
Я знаю, что бинарный поиск по отсортированному массиву будет выполнен в среднем O(logn), но какой будет лучший способ показать время выполнения O(logk), как описано выше, для отсортированного массива?
Я ценю любую помощь.
Сделайте экспоненциальный поиск, начиная с индекса m = 1, затем удваивая m каждый раз, пока элемент массива в m больше, чем x. Затем выполните обычный двоичный поиск в подмножестве массива ниже финального m.
Да, что-то в этом роде. –
@ user2580516 В чем заключается причина проведения экспоненциального поиска? –
@DerrekWhistle Независимость от общего количества предметов. Экспоненциальный поиск дает вам верхнюю границу для 'k', которая выключена не более чем в 2 раза, поэтому вы можете выполнять бинарный поиск на диапазоне длины O (k) независимо от того, насколько больше может быть n. – delnan
Бинарный поиск, предоставляющий O (log N), является стандартным подходом. Я не уверен, что O (log k) - это опечатка, полуэквивалентность или предполагает «смещение» поиска в сторону нижнего предела диапазона.
Может быть, бинарный поиск с использованием бесконтактного полпути серединой .. так как дифференциал log является log, возможно, используя log() функцию, чтобы выбрать среднюю точку на каждой итерации?
Являются ли ваши ключи произвольными значениями, или они являются целыми? – templatetypedef
Я не получаю O (logk) .. что делает k связано с сложностью O()? k - это просто значение индекса, правильно? Если этот x находится в индексе 0, я должен заполнить его в O (log0)? –
@DavidKernin Это именно то, что говорит O (log k): логарифмическое по k и, следовательно, (очень медленно) растет с ростом k. – delnan