Ctrl K

Поиск в сдвинутом массиве с повторами

Средняя
Был массив целых чисел, отсортированный по неубыванию; числа в нём могут повторяться. Его циклически сдвинули: какой-то хвост (возможно, пустой) переставили в начало. Например, [0, 2, 2, 5, 7] мог стать [5, 7, 0, 2, 2]. Результат — массив values. Верните True, если число value есть в values, иначе False. Сделайте как можно меньше шагов. Подумайте, как повторы влияют на скорость по сравнению со случаем различных чисел.
Пример 1
values=[6, 6, 8, 1, 3, 3, 6], value=3 → True

Это [1, 3, 3, 6, 6, 6, 8], сдвинутый так, что начинается с 6. Тройка в нём есть.

Пример 2
values=[6, 6, 8, 1, 3, 3, 6], value=5 → False

Пятёрки нет.

Пример 3
values=[4, 4, 4, 0, 4], value=0 → True
Ограничения
  • 1 ≤ len(values) ≤ 5000
  • -10⁴ ≤ values[i], value ≤ 10⁴
  • values — отсортированный по неубыванию массив, циклически сдвинутый
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПоиск в сдвинутом отсортированном массиве СредняяПервая и последняя копия СредняяПоиск в таблице-цепочке СредняяМинимум в сдвинутом списке СредняяЕдинственная вершина Средняя
загружаем Python…
Вход
values=[6, 6, 8, 1, 3, 3, 6], value=3
Ожидается
True

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 77 тестов на сервере, включая скрытые.