Find First and Last Position of Element in Sorted Array

Средняя№34оба края

Дан массив, отсортированный по неубыванию, так что равные числа стоят рядом, и искомое число. Нужно вернуть первый и последний индекс искомого или [−1, −1], если его нет, за O(log n). Наш пример: [1, 3, 3, 3, 3, 3, 6, 8] и 3 — ответ [1, 5].

34 Find First and Last Position of Element in Sorted ArrayРазбор · 1×

Пример: [1, 3, 3, 3, 3, 3, 6, 8], ищем края блока троек. Два поиска идут друг за другом; записанные совпадения остаются подсвеченными.

0113233343536678
ещё в диапазонесередина, проверяемотброшенозаписано: first или last

Ни одной тройки ещё не нашли: first = last = -1

01/32
сначала · назад · пуск · шаг
Скорость
1function searchRange(nums, target):
2 first = -1; last = -1
3 lo = 0; hi = len(nums) - 1
4 while lo <= hi: // search 1: the first target
5 mid = floor((lo + hi) / 2)
6 if nums[mid] < target: lo = mid + 1
7 else:
8 if nums[mid] == target: first = mid
9 hi = mid - 1 // an earlier one may exist
10 lo = 0; hi = len(nums) - 1
11 while lo <= hi: // search 2: the last target
12 mid = floor((lo + hi) / 2)
13 if nums[mid] > target: hi = mid - 1
14 else:
15 if nums[mid] == target: last = mid
16 lo = mid + 1 // a later one may exist
17 return [first, last]
состояние
first
-1
last
-1
lo
–
hi
–
mid
–
историянажмите шаг, чтобы вернуться

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

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

  1. Найти одну тройку мало: ответ — края блока троек. Поэтому при совпадении прогон записывает индекс и идёт дальше: влево в первом поиске, вправо во втором.
  2. В первом поиске всё левее lo меньше искомого, а всё правее hi — искомое или больше. Когда lo обгоняет hi, последнее записанное совпадение — самое левое. Второй поиск — зеркальный.
  3. Если остановиться на совпадении и шагать от него в стороны по одному, на массиве из одних троек выйдет O(n). Два поиска дают O(log n) при любом блоке.

Сложность

Время O(log n): два бинарных поиска друг за другом. Память O(1).

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

Решить на LeetCode ↗

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