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