Find Minimum in Rotated Sorted Array

Средняя№153повёрнутый массив

Отсортированный массив различных чисел повернули: несколько чисел из начала переехали в конец, не меняя порядка. Нужно найти наименьшее число за O(log n). Наш пример: [15, 18, 22, 3, 6, 9, 11] — ответ 3.

153 Find Minimum in Rotated Sorted ArrayРазбор · 1×

Пример: [15, 18, 22, 3, 6, 9, 11]: 3..22 по порядку, повёрнутые так, что начинаются с 15. Каждый шаг сравнивает nums[mid] с nums[hi].

015118222334659611lo
ещё в диапазонерастёт от mid до hiсередина, проверяемотброшеноминимум

lo — первый индекс, 0

01/16
сначала · назад · пуск · шаг
Скорость
1function findMin(nums):
2 lo = 0
3 hi = len(nums) - 1
4 while lo < hi:
5 mid = floor((lo + hi) / 2)
6 if nums[mid] > nums[hi]: // the drop is after mid
7 lo = mid + 1
8 else: // no drop: the minimum is mid or before
9 hi = mid
10 return nums[lo]
состояние
lo
0
hi
–
mid
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Повёрнутый отсортированный массив растёт, один раз падает и снова растёт. Минимум стоит сразу после спуска или на индексе 0, если спуска нет.
  2. Сравниваем середину с правым краем. Если nums[mid] > nums[hi], спуск между ними, и минимум правее mid. Если нет, mid..hi растёт без спуска, и минимум — mid или левее.
  3. Во втором случае hi = mid, а не mid − 1: mid сам может быть минимумом. Здесь уже первый mid попадает на 3, и диапазон потом сходится к нему.

Сложность

Время O(log n): каждый шаг делит диапазон пополам. Память O(1): три индекса.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.