Ctrl K

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

Средняя
Был массив различных целых чисел, отсортированный по возрастанию. Его, возможно, циклически сдвинули: взяли какой-то хвост и переставили в начало. Например, [1, 4, 6, 8, 9] мог превратиться в [8, 9, 1, 4, 6]. Результат — массив values. Верните индекс числа value в values или -1, если его там нет. Решение должно работать за O(log n).
Пример 1
values=[15, 18, 22, 3, 7, 11], value=7 → 4

Исходный список [3, 7, 11, 15, 18, 22] сдвинут так, что начинается с 15. Число 7 стоит на индексе 4.

Пример 2
values=[15, 18, 22, 3, 7, 11], value=16 → -1

Числа 16 нет, ответ -1.

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

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