Search in Rotated Sorted Array

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

Отсортированный массив различных чисел повернули: несколько чисел из начала переехали в конец, не меняя порядка. Нужно найти индекс искомого числа или вернуть −1, если его нет, за O(log n). Наш пример: [12, 19, 25, 31, 36, 2, 5, 9] и 5 — ответ 6.

33 Search in Rotated Sorted ArrayРазбор · 1×

Пример: [12, 19, 25, 31, 36, 2, 5, 9]: 2..36 по порядку, повёрнутые так, что начинаются с 12. Ищем 5. Скобка отмечает половину, которая растёт без спуска.

012119225331436526579lo
ещё в диапазонерастёт без спускасередина, проверяемотброшенонайдено

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

01/19
сначала · назад · пуск · шаг
Скорость
1function search(nums, target):
2 lo = 0
3 hi = len(nums) - 1
4 while lo <= hi:
5 mid = floor((lo + hi) / 2)
6 if nums[mid] == target:
7 return mid
8 if nums[lo] <= nums[mid]: // lo..mid rises
9 if nums[lo] <= target < nums[mid]: hi = mid - 1
10 else: lo = mid + 1
11 else: // mid..hi rises
12 if nums[mid] < target <= nums[hi]: lo = mid + 1
13 else: hi = mid - 1
14 return -1
состояние
lo
0
hi
–
mid
–
историянажмите шаг, чтобы вернуться

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

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

  1. Если разрезать повёрнутый массив на mid, хотя бы одна сторона растёт без спуска. nums[lo] <= nums[mid] значит, что левая, иначе — правая.
  2. В растущем куске лежат ровно значения между его краями, поэтому одна проверка показывает, может ли там быть искомое. Если да, оставляем эту половину, если нет — оно может быть только в другой.
  3. В любом случае половина диапазона уходит, как в обычном бинарном поиске. Здесь первый шаг отбрасывает левую половину 12..31, а второй находит 5 между 2 и 9.

Сложность

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

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

Решить на LeetCode ↗

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