Войти Регистрация
Алгоритмы

137. Операция в кольцевом буфере

Средняя

Сервис уведомлений Альфа‑Банка хранит последние операции в кольцевом буфере. Номера операций растут, но запись идёт по кругу, поэтому массив ids — отсортированный по возрастанию список, сдвинутый циклически: например [7041, 7042, 7043, 7037, 7038, 7039, 7040].

Все номера разные. Верните позицию номера target в ids или −1, если его нет. Нужно O(log n).

В работе: Клиент жмёт на пуш об операции 7038 — сервис достаёт её из буфера на 50 000 записей без полного просмотра.

Пример 1

Ввод
ids = [7041, 7042, 7043, 7037, 7038, 7039, 7040]
target = 7038
Вывод
4

Разрыв после 7043, номер 7038 — в позиции 4.

Пример 2

Ввод
ids = [7041, 7042, 7043, 7037, 7038, 7039, 7040]
target = 7036
Вывод
-1

Такой операции уже нет в буфере.

Ограничения

  • 0 ≤ n ≤ 10⁵
  • номера различны
  • массив — циклический сдвиг возрастающего
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def find_in_ring(ids, target):
Бинарный поискПовёрнутый массивцельlogn

Источник: наша задача на данных Альфа-Банка. Условие пересказано своими словами.