Алгоритмическая задачка (гугл стайл)

Nonnik

Есть отсортированный (по возрастанию) массив целых чисел. Массив циклически сдвигают на К вправо. К мы не знаем.
Надо найти алгоритм поиска элемента в этом массиве. Алгоритм должен иметь минимально возможную сложность.
Можно за логарифм?

vsjshnikova

Можно же K найти за логарифм

Nonnik

Продолжаю думать, что нельзя в общем случае. Что если все элементы одинаковые?

vsjshnikova

Продолжаю думать, что нельзя в общем случае. Что если все элементы одинаковые?
Да, действительно. Если элементы различны, то можно за логарифм, если нет - то хз. Надо думать дальше.

Vlad128

если все элементы — 0, а один — 1 и надо найти 1, то меньше O(N) не получится.
Стоит подумать о рандомизованных алгоритмах.

obushmelev

меньше O(1) не получится.
Наверное, ты O(n) имел ввиду?
А нет решения, чтобы не находить К сначала?

Vlad128

так причем тут поиск K?
вообще никак не получится :grin:
Ну точнее K = искомому индексу, так что нет, не получится =)

Vlad128

Впрочем, там написано "по возрастанию". Так что все как ты сказал.
Оставить комментарий
Имя или ник:
Комментарий: