Find First and Last Position of Element in Sorted Array
Дан список целых чисел nums, отсортированный в неубывающем порядке, поэтому значения могут повторяться, и целое число target. Верните список из двух индексов, считая с 0: первой и последней позиции, в которой встречается target. Если target нет в списке, верните [-1, -1]. Стремитесь к временной сложности O(log n).
Функция
- numsinteger-array
- отсортированный список целых чисел, в котором значения могут повторяться
- targetinteger
- значение, которое нужно найти
- Возвращаетinteger-array
- первый и последний индексы target или [-1, -1], если он отсутствует
Ограничения
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsотсортирован в порядке неубывания.
Примеры
- Ввод
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- Вывод
- [1, 3]
- Пояснение
- Три копии числа 5 находятся по индексам 1, 2 и 3, поэтому последовательность начинается с индекса 1 и заканчивается индексом 3. По индексу 0 находится 3, а по индексу 4 — 8, поэтому последовательность не может продолжаться дальше.
- Ввод
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- Вывод
- [-1, -1]
- Пояснение
- 7 находилась бы между 5 с индексом 3 и 8 с индексом 4, и ни одно из них не равно 7. В списке нет копии, поэтому ответ —
[-1, -1].
Дополнительный вопрос
Если к одному и тому же списку поступают тысячи запросов для разных целей, может ли один предварительный проход по нему сделать каждый запрос быстрее, чем O(log n)?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Поскольку
numsотсортирован, все копииtargetрасположены рядом друг с другом в одном непрерывном участке. Тебе нужны оба конца этого участка.Поиск одной копии с последующим просмотром элементов в обе стороны может потребовать
O(n), если серия длинная. Вместо этого измените бинарный поиск так, чтобы после совпадения он продолжал двигаться влево: тогда он остановится на первом индексе, значение которого не меньше искомого числа.Напиши одну вспомогательную функцию, которая возвращает первый индекс, для которого
nums[i] ≥ value. Вызови её сtarget, чтобы получить начало последовательности, проверь, что значение там равноtarget, и вызови её сtarget + 1: последовательность заканчивается на один индекс раньше.
Решение
Обычный бинарный поиск останавливается на первой найденной копии target, которая может находиться где угодно в последовательности. Вместо этого найдите нижнюю границу: первый индекс, значение которого не меньше заданного числа. Нижние границы для target и target + 1 дают оба конца последовательности за O(log n).
Просканируй весь список
Идея
Пройдите по списку один раз. Первый индекс, на котором находится target, — это начало, а последний — конец. Если target ни разу не встречается, оба остаются равными -1.
Это работает с любым списком — отсортированным или нет, — и в этом его недостаток: приходится просматривать все n значений. Для списка из 10^4 значений потребуется 10 000 сравнений, хотя достаточно было бы примерно 28.
Алгоритм
- Установи
first = last = -1. - Для каждого индекса
i, еслиnums[i]равенtarget, установиfirst = i, еслиfirstвсё ещё равен-1, и установиlast = i. - Верни
[first, last].
def searchRange(nums, target):
first = last = -1
for i, value in enumerate(nums):
if value == target:
if first == -1:
first = i # the first match fixes the start
last = i # every later match moves the end
return [first, last]Найди одну копию, затем разверни
Идея
Выполни бинарный поиск любого индекса, в котором находится target. Список отсортирован, поэтому все его вхождения образуют один непрерывный диапазон вокруг этого индекса: двигайся влево и вправо, пока соседний элемент равен target.
Поиск требует O(log n), а обход — по одному шагу на каждое вхождение, всего k. Если большая часть списка состоит из target, например 10^4 вхождений, обход прочитает каждое значение, и ты вернёшься к линейному поиску.
Алгоритм
- Выполните бинарный поиск любого индекса
found, для которогоnums[found] == target. - Если такого индекса нет, верните
[-1, -1]. - Сдвигайте
firstвлево отfound, пока значение перед ним равноtarget. - Сдвигайте
lastвправо отfound, пока значение после него равноtarget. - Верните
[first, last].
def searchRange(nums, target):
# An ordinary binary search finds some copy of target, if there is one.
lo, hi = 0, len(nums) - 1
found = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
found = mid
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
if found == -1:
return [-1, -1]
# The copies sit next to each other, so walk out to both ends of the run.
first = last = found
while first > 0 and nums[first - 1] == target:
first -= 1
while last < len(nums) - 1 and nums[last + 1] == target:
last += 1
return [first, last]Два бинарных поиска нижней границы
Идея
Зададим другой вопрос: каков первый индекс, значение по которому не меньше value? Этот индекс — нижняя граница, или n, если подходящего значения нет. Поддерживай полуинтервал [lo, hi), который всегда содержит этот индекс. Если nums[mid] < value, значит, mid и все элементы перед ним слишком малы. Иначе mid подходит, но может подойти и более ранний индекс, поэтому mid остаётся в диапазоне как новое значение hi. Цикл никогда не завершается досрочно при совпадении.
Нижняя граница target — это место, где начинается его последовательность. Значения — целые числа, поэтому первое значение, большее target, находится на нижней границе target + 1, а последовательность заканчивается на один индекс раньше. В первом примере нижняя граница 5 равна 1, а нижняя граница 6 равна 4, где находится 8: последовательность — [1, 3]. Два поиска занимают около 28 шагов для 10^4 значений независимо от длины последовательности.
Алгоритм
- Напиши
lowerBound(value): начни сlo = 0,hi = n; покаlo < hi, еслиnums[mid] < value, установиlo = mid + 1, иначе установиhi = mid; верниlo. - Установи
first = lowerBound(target). - Если
first == nилиnums[first] != target, верни[-1, -1]. - Установи
last = lowerBound(target + 1) - 1и верни[first, last].
def lowerBound(nums, value):
# The first index whose number is at least value, or len(nums) if none is.
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < value:
lo = mid + 1 # nums[mid] and everything before it is too small
else:
hi = mid # nums[mid] qualifies, but an earlier index might too
return lo
def searchRange(nums, target):
first = lowerBound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
# The run of target ends right before the first number above target.
last = lowerBound(nums, target + 1) - 1
return [first, last]
Ловушки и крайние случаи
- Возврат сразу после
nums[mid] == target. Этот индекс может находиться где угодно в последовательности: в[3, 5, 5, 5, 8]первый средний индекс равен 2, то есть он не является ни одним из концов. - Запись
hi = mid - 1при поиске нижней границы, когдаnums[mid] ≥ value. Это отбрасываетmid, который может быть ответом. - Чтение
nums[first]без проверкиfirst < n. Еслиtargetбольше любого значения, как 13 в примерах, нижняя граница равнаn— индексу сразу за концом. - Забывать о сдвиге в Lua и R. Их списки начинаются с 1, поэтому нужно вычесть 1 из обеих позиций.
Частые вопросы3
Какова временная сложность поиска первого и последнего вхождения?
Время O(log n) и память O(1), при этом выполняются два двоичных поиска. Ни один из них не останавливается при совпадении, поэтому затраты не зависят от количества копий целевого значения: около 14 шагов на поиск для 10^4 значений.
Что такое нижняя граница в бинарном поиске?
Нижняя граница значения — это первый индекс, элемент которого не меньше этого значения, или длина списка, если такого элемента нет. Это место, куда было бы вставлено значение, чтобы список оставался отсортированным. Верхняя граница — это первый индекс, элемент которого строго больше.
Может ли одна функция бинарного поиска находить и первый, и последний индекс?
Да. Добавь к поиску флаг: при совпадении запиши индекс и продолжай искать влево, чтобы найти первое вхождение, или вправо — чтобы найти последнее. Также работает вызов поиска нижней границы для target и для target + 1. Оба варианта выполняются за O(log n).
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def searchRange(nums, target):
# Напишите код здесьТест #1
Тест #2
Аргументы
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
Ожидаемый вывод
[1, 3]