Поиск в отсортированном повернутом массиве
Дан массив длины n, который изначально был отсортирован по возрастанию, а затем повернут от 1 до n раз. Например, массив nums = [1,2,3,4,5,6] мог стать:
- [3,4,5,6,1,2] если его повернули 4 раза
- [1,2,3,4,5,6] если его повернули 6 раз
Дан повернутый отсортированный массив nums и целое число target, верните индекс target в массиве nums или -1, если такого элемента нет.
Можно считать, что все элементы в отсортированном повернутом массиве nums уникальны.
Тривиальное решение работает за O(n), можете ли вы написать алгоритм, который работает за O(log n)?
Пример 1:
Input: nums = [3,4,5,6,1,2], target = 1
Output: 4
Пример 2:
Input: nums = [3,5,6,0,1,2], target = 4
Output: -1
Рекомендуемая временная и пространственная сложность
Оптимальное решение имеет временную сложность O(log n) и пространственную сложность O(1), где n — размер входного массива.
Подсказка 1
Линейный поиск даст нам O(n). Для достижения O(log n) подумайте о бинарном поиске. Как его можно модифицировать для работы с повернутым массивом?
Подсказка 2
В любой точке массива одна половина всегда будет отсортирована. Как это можно использовать?
Подсказка 3
Определив, какая половина отсортирована, мы можем проверить, находится ли целевое значение в этом диапазоне. Если да - ищем там, если нет - в другой половине.