Поиск в повёрнутых массивьях, поиск пика, поиск минимума.
Поиск границ в отсортированных массивах и поиск в повёрнутых массивах.
Условие:
Отсортированный по возрастанию массив nums был повёрнут в некоторой точке. Например, [0, 1, 2, 4, 5, 6, 7] может стать [4, 5, 6, 7, 0, 1, 2].
Дан повёрнутый массив nums и целевое значение target. Если target найден в массиве, верните его индекс. В противном случае верните -1.
Примеры:
Ввод: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Вывод: 4
Ввод: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Вывод: -1
Решение:
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# Левая половина отсортирована
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Правая половина отсортирована
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1Объяснение:
nums[left] <= nums[mid] — левая половина отсортированаСложность: O(log n)
Условие:
Отсортированный по возрастанию массив nums был повёрнут в некоторой точке. Найдите минимальный элемент в этом повёрнутом массиве.
Примеры:
Ввод: nums = [3, 4, 5, 1, 2]
Вывод: 1
Ввод: nums = [4, 5, 6, 7, 0, 1, 2]
Вывод: 0
Решение:
def findMin(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
# Если mid > right, минимум в правой половине
if nums[mid] > nums[right]:
left = mid + 1
# Иначе минимум в левой половине (включая mid)
else:
right = mid
return nums[left]Объяснение:
nums[mid] с nums[right]nums[mid] > nums[right] — минимум справа от midleft < right (не <=), так как ищем точку сходаСложность: O(log n)
Условие: Пиковый элемент — это элемент, который строго больше своих соседей.
Дан целый массив nums. Найдите пиковый элемент и верните его индекс. Если в массиве несколько пиков, верните индекс любого из них.
Примеры:
Ввод: nums = [1, 2, 3, 1]
Вывод: 2
Ввод: nums = [1, 2, 1, 3, 5, 6, 4]
Вывод: 5
Решение:
def findPeakElement(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
# Сравниваем с правым соседом
if nums[mid] < nums[mid + 1]:
# Пик справа
left = mid + 1
else:
# Пик слева (включая mid)
right = mid
return leftОбъяснение:
nums[mid] с nums[mid + 1]nums[mid] < nums[mid + 1] — идём вправо (там точно есть пик)Сложность: O(log n)
| Задача | Ключевая идея |
|---|---|
| Rotated Search | Определить отсортированную половину |
| Find Minimum | Сравнивать mid с right |
| Find Peak | Сравнивать mid с mid+1 |
# ❌ Неправильно
if nums[left] < nums[mid]: # Не включает равенство!
# ✅ Правильно
if nums[left] <= nums[mid]: # Включает равенство# ❌ Неправильно
while left <= right: # Может зациклиться
# ✅ Правильно
while left < right: # Ищем точку сходаBinary Search: Границы и повёрнутые массивы — поиск в модифицированных отсортированных массивах.
Ключевые принципы:
Далее: Binary Search: Поиск ответа