Сложность: Medium
Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:
[4,5,6,7,0,1,2], если он был повернут 4 раза.
[0,1,2,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива.
Вы должны написать алгоритм, который работает за время O(log n).
Пример:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
👨💻 Алгоритм:
1️⃣Нахождение середины массива: Определите элемент, находящийся посередине массива.
2️⃣Определение направления поиска: Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины. Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины.
3️⃣Остановка поиска при нахождении точки перегиба: Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий: nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом. nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом.
😎 Решение:
class Solution:
def findMin(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
left = 0
right = len(nums) - 1
if nums[right] > nums[0]:
return nums[0]
while right >= left:
mid = left + (right - left) // 2
if nums[mid] > nums[mid + 1]:
return nums[mid + 1]
if nums[mid - 1] > nums[mid]:
return nums[mid]
if nums[mid] > nums[0]:
left = mid + 1
else:
right = mid - 1
Ставь 👍 и забирай 📚 Базу знаний