MiddleКодЧастоЕщё не отвечали
Найти максимум циклически сдвинутого отсортированного массива за O(log n)
Отсортированный массив различных целых был циклически сдвинут на некоторое число позиций (возможно, 0). Найдите его максимальный элемент.
Требования:
- O(log n) время — вариация бинарного поиска, а не линейный проход.
- Обработайте случай без сдвига (сдвиг
0).
def rotated_max(nums):
# ваш код здесьДопишите реализацию.
Бинарный поиск точки сдвига. Сравните nums[mid] с nums[high]: если nums[mid] > nums[high], пик в правой половине (low = mid + 1), иначе он в mid или левее (high = mid). Максимум — элемент прямо перед точкой сдвига: nums[low - 1], когда low встанет на минимум. O(log n); отсортированный массив без сдвига вернёт свой последний элемент.
- ✗Скатываться к линейному проходу O(n) вместо бинарного поиска
- ✗Считать, что максимум всегда в индексе
0или последнем - ✗Неверно обрабатывать сдвиг
0, когда массив уже отсортирован
- →Почему сравнения
nums[mid]сnums[high]достаточно для выбора половины? - →Как меняется подход, если допускаются повторяющиеся значения?
Оглавление
Задача
Реализуйте rotated_max: найдите максимум циклически сдвинутого отсортированного массива различных целых за O(log n).
Решение
def rotated_max(nums):
low, high = 0, len(nums) - 1
while low < high:
mid = (low + high) // 2
if nums[mid] > nums[high]: # пик в правой половине
low = mid + 1
else: # пик в mid или левее
high = mid
# low указывает на минимум; максимум — элемент перед ним
return nums[low - 1]Ключевые моменты
- Сравнение
nums[mid]сnums[high]определяет, в какой половине точка сдвига. lowсходится к минимуму; максимум —nums[low - 1]по модулю длины.- Массив без сдвига вырождается в обычный бинарный поиск и даёт последний элемент.
Оглавление
