Find First and Last Position of Element in Sorted Array
Você recebe uma lista de números inteiros nums ordenada em ordem não decrescente, portanto um valor pode se repetir, e um número inteiro target. Retorne uma lista com dois índices, começando em 0: a primeira e a última posição em que target aparece. Se target não estiver na lista, retorne [-1, -1]. Procure alcançar tempo O(log n).
Função
- numsinteger-array
- a lista ordenada de números inteiros, que pode conter valores repetidos
- targetinteger
- o valor a procurar
- Retornainteger-array
- o primeiro e o último índice de target, ou [-1, -1] se ele não estiver presente
Restrições
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsestá ordenado em ordem não decrescente.
Exemplos
- Entrada
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- Saída
- [1, 3]
- Explicação
- As três cópias de 5 estão nos índices 1, 2 e 3, então a sequência começa em 1 e termina em 3. O índice 0 contém 3 e o índice 4 contém 8, então a sequência não pode se estender mais.
- Entrada
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- Saída
- [-1, -1]
- Explicação
- 7 ficaria entre 5 no índice 3 e 8 no índice 4, e nenhum deles é 7. A lista não contém nenhuma cópia, então a resposta é
[-1, -1].
Para ir além
Se a mesma lista receber milhares de consultas para diferentes valores-alvo, uma única passagem prévia por ela pode tornar cada consulta mais rápida que O(log n)?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Como
numsestá ordenado, todas as cópias detargetficam juntas em uma sequência. Você precisa encontrar as duas extremidades dessa sequência.Encontrar uma ocorrência e percorrer para fora pode custar
O(n)quando a sequência é longa. Em vez disso, altere a busca binária para que ela continue indo para a esquerda após encontrar uma correspondência: assim, ela para no primeiro índice cujo valor é pelo menos o número que você está procurando.Escreva uma função auxiliar que retorne o primeiro índice com
nums[i] ≥ value. Chame-a comtargetpara obter o início da sequência, verifique se o valor nesse índice étargete chame-a comtarget + 1: a sequência termina um índice antes disso.
Solução
Uma busca binária simples para na primeira ocorrência de target que encontra, e essa ocorrência pode estar em qualquer posição da sequência. Em vez disso, procure um limite inferior: o primeiro índice cujo valor é maior ou igual a um determinado número. Os limites inferiores de target e target + 1 fornecem as duas extremidades da sequência em O(log n).
Examine a lista inteira
Intuição
Percorra a lista uma vez. O primeiro índice que contém target é o início, e o último é o fim. Se target nunca aparecer, ambos continuam sendo -1.
Isso funciona com qualquer lista, ordenada ou não, e essa é sua desvantagem: lê todos os n valores. Uma lista de 10^4 valores custa 10.000 comparações, quando cerca de 28 seriam suficientes.
Algoritmo
- Defina
first = last = -1. - Para cada índice
i, senums[i]for igual atarget, definafirst = iquandofirstainda for-1e definalast = i. - Retorne
[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]Encontre uma cópia e, em seguida, expanda
Intuição
Faça uma busca binária por qualquer índice que contenha target. A lista está ordenada, então todas as cópias ficam em uma sequência contínua ao redor desse índice: avance para a esquerda e para a direita enquanto o vizinho ainda for target.
A busca custa O(log n) e a caminhada custa uma etapa por cópia, k ao todo. Quando a maior parte da lista é target, digamos, 10^4 cópias, a caminhada lê todos os valores e você acaba fazendo uma busca linear.
Algoritmo
- Faça uma busca binária por qualquer índice
foundem quenums[found] == target. - Se não houver nenhum, retorne
[-1, -1]. - Mova
firstpara a esquerda a partir defoundenquanto o valor anterior for igual atarget. - Mova
lastpara a direita a partir defoundenquanto o valor seguinte for igual atarget. - Retorne
[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]Duas buscas binárias pelo limite inferior
Intuição
Faça uma pergunta diferente: qual é o primeiro índice cujo valor é pelo menos value? Esse índice é o limite inferior, ou n se nenhum valor se qualificar. Mantenha um intervalo semiaberto [lo, hi) que sempre o contenha. Se nums[mid] < value, então mid e tudo antes dele são pequenos demais. Caso contrário, mid se qualifica, mas um índice anterior também pode se qualificar, então mid permanece no intervalo como o novo hi. O loop nunca para antecipadamente ao encontrar uma correspondência.
O limite inferior de target é onde sua sequência começa. Os valores são inteiros, então o primeiro valor maior que target está no limite inferior de target + 1, e a sequência termina um índice antes dele. No primeiro exemplo, o limite inferior de 5 é 1 e o limite inferior de 6 é 4, onde está 8: a sequência é [1, 3]. As duas buscas levam cerca de 28 etapas para 10^4 valores, independentemente do comprimento da sequência.
Algoritmo
- Escreva
lowerBound(value): comece comlo = 0,hi = n; enquantolo < hi, senums[mid] < value, definalo = mid + 1; caso contrário, definahi = mid; retornelo. - Defina
first = lowerBound(target). - Se
first == nounums[first] != target, retorne[-1, -1]. - Defina
last = lowerBound(target + 1) - 1e retorne[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]
Armadilhas e casos extremos
- Retornar assim que
nums[mid] == target. Esse índice pode estar em qualquer posição na sequência: em[3, 5, 5, 5, 8], o primeiro elemento do meio está no índice 2, que não é nenhuma das extremidades. - Escrever
hi = mid - 1na busca pelo limite inferior quandonums[mid] ≥ value. Isso descartamid, que pode ser a resposta. - Ler
nums[first]sem verificarfirst < n. Quandotargeté maior que todos os valores, como 13 seria nos exemplos, o limite inferior én, uma posição além do fim. - Esquecer o deslocamento em Lua e R. As listas dessas linguagens começam em 1, então subtraia 1 das duas posições.
Perguntas frequentes3
Qual é a complexidade de tempo para encontrar a primeira e a última posição?
Tempo O(log n) e espaço O(1), com duas buscas binárias. Nenhuma delas para ao encontrar uma correspondência, então o custo não depende de quantas cópias do valor-alvo existem: cerca de 14 etapas por busca para 10^4 valores.
O que é um limite inferior na busca binária?
O limite inferior de um valor é o primeiro índice cujo elemento é maior ou igual a esse valor, ou o comprimento da lista, se não houver nenhum. É onde o valor seria inserido para manter a lista ordenada. O limite superior é o primeiro índice cujo elemento é estritamente maior.
Uma única função de busca binária pode encontrar tanto o primeiro quanto o último índice?
Sim. Passe uma flag para a busca: ao encontrar uma correspondência, registre o índice e continue buscando à esquerda para encontrar a primeira ocorrência ou à direita para encontrar a última. Também funciona fazer uma busca de limite inferior por target e por target + 1. Ambas têm complexidade O(log n).
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def searchRange(nums, target):
# Escreva o código aquiTeste #1
Teste #2
Argumentos
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
Saída Esperada
[1, 3]