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

Sebasten

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

Vlad77

находишь за логарифм место стыка. После этого за логарифм можешь искать элемент

lubanj

находишь за логарифм место стыка

подробнее пожалуйста

Serab

Давайте общаться там, в стади =]

Vlad77

i=0, j=n

пока a[i] > a[j]

  если a[(i+j)/2] > a[j] то i = (i+j)/2

  иначе j= (i+j)/2

как-то так. Или у меня глюки?

Serab

А хотя там же написано по возрастанию, так что это верное решение для случая, когда все элементы различны, да =)

Sebasten

Эт не пашет для последовательности
11121
когда ищем двойку

vall

она ну никак не может быть возрастающей =)

Vlad77

Ну тогда и спрашивай: есть массив из n-1 нулей и одной единицей. Найти за логарифм единицу
чего лукавишь?

Sebasten

Ок. Для возрастающей всё работает за логарифм. Что с неубывающей?

SEMEN73

С неубывающей очевидно O(n). Ибо ту самую одну единицу, не зная k, ты кроме как полным перебором найти не сможешь.

agaaaa

Ну тогда и спрашивай: есть массив из n-1 нулей и одной единицей. Найти за логарифм единицу
чего лукавишь?

Из этого поста разве не очевидно, что O(n)?

Sebasten

Ок. Успокоился. Всем спасибо за участие (в стади тоже

Andbar

Разве с неубывающим массивом в каких-то случаях, помимо равенства первого и последнего элементов, сложность деградирует с логарифма до O(n)?

danilov

> она ну никак не может быть возрастающей =)
Ну, формально нигде не сказано, что массив возрастающий, сказано, что он отсортирован по возрастанию.
Или массив [1, 2, 1] запрещается сортировать по возрастанию?