Search Insert Position

Лёгкая№35найти число

Дан отсортированный массив различных чисел и искомое число. Нужно вернуть его индекс, если оно есть, а если нет — индекс, куда его вставить, чтобы порядок не сломался. И всё за O(log n). Наш пример: [1, 4, 6, 9, 13, 17] и 10 — ответ 4: 10 встанет между 9 и 13.

35 Search Insert PositionРазбор · 1×

Пример: [1, 4, 6, 9, 13, 17], куда встанет 10? Пустая клетка 6 — место после последнего числа.

011426394135176lo
место ещё может быть здесьсередина, проверяемотброшеноместо для 10

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

01/16
сначала · назад · пуск · шаг
Скорость
1function searchInsert(nums, target):
2 lo = 0
3 hi = len(nums) // the target may go after the end
4 while lo < hi:
5 mid = floor((lo + hi) / 2)
6 if nums[mid] < target:
7 lo = mid + 1 // the place is after mid
8 else:
9 hi = mid // mid may be the place: keep it
10 return lo
состояние
lo
0
hi
–
mid
–
историянажмите шаг, чтобы вернуться

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

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

  1. Ответ — первый индекс, где число не меньше искомого: само искомое, если оно есть, или следующее за ним большее. Если все числа меньше, это место за концом, поэтому hi начинается с len(nums).
  2. Если nums[mid] < target, место правее mid: lo = mid + 1. Иначе mid сам может оказаться этим местом, и hi = mid оставляет его в диапазоне.
  3. Всё до lo меньше искомого, а всё начиная с hi — нет. Когда lo встречает hi, эта граница и есть ответ, нашлось число или нет.

Сложность

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

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

Решить на LeetCode ↗

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