Массив из различных чисел был отсортирован по возрастанию, а затем
циклически сдвинут на неизвестное число позиций: например, [0,1,2,4,5,6,7]
мог превратиться в [4,5,6,7,0,1,2]. Найдите индекс элемента target или
верните -1, если его нет.
// Search возвращает индекс target в повёрнутом отсортированном nums или -1.
func Search(nums []int, target int) int
Примеры
nums = [4,5,6,7,0,1,2], target = 0 → 4
nums = [4,5,6,7,0,1,2], target = 3 → -1
nums = [1], target = 0 → -1
nums = [1,3], target = 3 → 1 (сдвиг на 0 — тоже «поворот»)
Ограничения
0 ≤ len(nums) ≤ 10⁶, все элементы различны, любые int.- Массив менять нельзя.
- Ожидается O(log n) на запрос: функцию вызывают много раз на одном
большом массиве, линейный поиск (в том числе поиск точки поворота проходом)
не уложится по времени.