Search in Rotated Sorted Array
Uma lista de inteiros distintos foi ordenada em ordem crescente e depois rotacionada: uma quantidade de elementos, possivelmente zero, foi retirada do início e movida para o final na mesma ordem. Por exemplo, [2, 5, 8, 11, 15, 19, 23] rotacionada em 4 posições se torna [15, 19, 23, 2, 5, 8, 11]. Você recebe a lista rotacionada nums e um inteiro target. Retorne o índice de target em nums, contando a partir de 0, ou -1 se ele não estiver na lista, em tempo O(log n).
Função
- numsinteger-array
- a lista ordenada e rotacionada de números inteiros distintos
- targetinteger
- o valor a ser procurado
- Retornainteger
- o índice de target em nums, ou -1 se estiver ausente
Restrições
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- Todos os valores em
numssão distintos. numsé uma lista crescente rotacionada por algumkcom0 ≤ k < nums.length;k = 0a mantém sem rotação.
Exemplos
- Entrada
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- Saída
- 4
- Explicação
- 5 está no índice 4. O primeiro elemento do meio, índice 3, contém 2, então a metade direita
[2, 5, 8, 11]é a parte ordenada, e 5 está entre 2 e 11. O próximo elemento do meio, índice 5, contém 8; a parte esquerda ordenada[5, 8]contém 5, o que leva ao índice 4.
- Entrada
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- Saída
- -1
- Explicação
- 65 ficaria entre 60 e 70, e nenhum elemento contém esse valor. O primeiro elemento do meio, 70 no índice 3, coloca 65 dentro da parte ordenada à esquerda
[40, 50, 60, 70]. O intervalo diminui dentro desse trecho até ficar vazio, então a função retorna-1.
- Entrada
- nums = [8, 13, 21, 1, 3, 5]target = 13
- Saída
- 1
- Explicação
- O primeiro elemento do meio, no índice 2, contém 21. A parte esquerda
[8, 13, 21]está ordenada e 13 está entre 8 e 21, então toda a parte direita é descartada. A busca então encontra 13 no índice 1.
+23 testes ocultos ao enviar
Para ir além
Se nums puder conter duplicatas, nenhum algoritmo poderá garantir O(log n). Você consegue provar isso? Crie uma lista rotacionada de 1s com um único 0 escondido nela, em que qualquer busca por 0 precise ler todos os elementos.
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Escolha qualquer índice do meio e observe as duas metades de cada lado dele. A rotação criou um ponto em que os valores diminuem, do maior para o menor. As duas metades podem conter essa queda?
Pelo menos uma metade está sempre ordenada, e comparar
nums[lo]comnums[mid]indica qual delas. Para uma metade ordenada, você pode verificar em uma etapa setargetestá entre o primeiro e o último valor dela.Mantenha
loehiao redor da parte que ainda pode contertarget. A cada etapa, se o intervalo de valores da metade ordenada contivertarget, mantenha essa metade; caso contrário, mantenha a outra. Pare quando encontrartargetou quando o intervalo estiver vazio.
Solução
Uma lista ordenada e rotacionada consiste em dois trechos ordenados colocados um após o outro: [15, 19, 23] e depois [2, 5, 8, 11]. A busca binária simples não funciona nela, porque comparar target com o valor do meio não indica mais em qual lado está target. A solução se baseia em um fato: onde quer que você divida a lista, pelo menos uma das duas metades está totalmente ordenada e, para uma metade ordenada, você pode determinar com uma comparação se target pode estar nela.
Examine cada elemento
Intuição
Verifique cada índice em ordem e retorne o primeiro cujo valor seja igual a target. Se o loop terminar sem encontrar uma correspondência, retorne -1. Os valores são distintos, então a primeira correspondência é a única, e a busca está correta para qualquer lista, com rotação ou não.
Isso ignora tudo o que o problema informa. A lista é formada por dois trechos ordenados, mas a busca percorre até todos os 5000 elementos, enquanto uma busca binária precisa de cerca de 13 comparações. A diferença aumenta com a entrada: um milhão de elementos custa um milhão de comparações, contra cerca de 20. A tarefa pede O(log n), então esta é a solução básica a ser aprimorada, não a resposta.
Algoritmo
- Para cada índice
ide 0 an-1, comparenums[i]comtarget. - Se forem iguais, retorne
i. - Após o loop, retorne
-1.
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1Encontre o ponto de rotação e, em seguida, faça uma busca binária
Intuição
A lista rotacionada contém duas sequências ordenadas, e a segunda começa pelo menor valor. Chame seu índice de k. Depois que você souber k, o problema se transforma em uma busca binária simples: nums[k..n-1] está ordenada e contém os valores de nums[k] a nums[n-1], e nums[0..k-1] está ordenada e contém todos os valores maiores. Uma comparação de target com nums[k] e nums[n-1] determina em qual sequência procurar.
Para encontrar k, faça uma busca binária pelo ponto de queda. Compare o valor do meio com o último valor do intervalo, nums[hi]. Se nums[mid] > nums[hi], os valores diminuem em algum ponto após mid, então o menor valor está à direita dele: defina lo = mid + 1. Caso contrário, nums[mid..hi] cresce sem uma queda, então o menor valor está em mid ou antes dele: defina hi = mid, mantendo mid no intervalo. Quando lo encontrar hi, esse índice será k.
Acompanhe o primeiro exemplo, [15, 19, 23, 2, 5, 8, 11] com target = 5. O valor do meio, 2, não é maior que 11, então hi passa a ser 3; depois, 19 é maior que 2, então lo passa a ser 2; em seguida, 23 é maior que 2, então lo passa a ser 3, e k = 3. Como 5 está entre nums[3] = 2 e nums[6] = 11, procure nos índices de 3 a 6, onde a busca binária encontra 5 no índice 4. Duas buscas binárias custam cerca de 2 log2 n etapas.
Algoritmo
- Defina
lo = 0ehi = n-1. Enquantolo < hi, calculemid; senums[mid] > nums[hi], definalo = mid + 1; caso contrário, definahi = mid. - Chame o índice final de
k: ele contém o menor valor. - Se
nums[k] ≤ target ≤ nums[n-1], pesquise os índices dekan-1; caso contrário, pesquise os índices de 0 ak-1. - Execute uma busca binária simples nesse intervalo e retorne o índice de
target, ou-1se o intervalo ficar vazio.
def search(nums, target):
n = len(nums)
# 1. Find k, the index of the smallest value, where the second run starts.
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop is right of mid
else:
hi = mid # mid is in the low run: the minimum is at mid or left of it
k = lo
# 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
if nums[k] <= target <= nums[n - 1]:
lo, hi = k, n - 1
else:
lo, hi = 0, k - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Uma busca binária na metade ordenada
Intuição
Você não precisa saber onde está o ponto de rotação. Mantenha a promessa habitual da busca binária: se target estiver na lista, seu índice estará entre lo e hi. Observe o índice do meio, mid. Os valores diminuem apenas uma vez em toda a lista, então essa queda está em, no máximo, uma das duas metades ao redor de mid, e a outra metade está ordenada.
Encontre a metade ordenada com uma comparação. Se nums[lo] ≤ nums[mid], a metade esquerda nums[lo..mid] não tem nenhuma queda e está ordenada. Como você já sabe que nums[mid] não é target, target só pode estar nessa metade se nums[lo] ≤ target < nums[mid]. Se estiver, defina hi = mid - 1; caso contrário, target só pode estar na outra metade, então defina lo = mid + 1. Quando nums[lo] > nums[mid], a queda está à esquerda, a metade direita nums[mid..hi] está ordenada, e o teste espelhado nums[mid] < target ≤ nums[hi] decide. Você nunca raciocina diretamente sobre a metade desordenada: target só fica nela quando não pode estar na metade ordenada.
Acompanhe o primeiro exemplo, [15, 19, 23, 2, 5, 8, 11] com target = 5. O intervalo de 0 a 6 tem índice do meio 3, com valor 2. Como 15 é maior que 2, a metade direita [2, 5, 8, 11] está ordenada, e 5 está nela, então lo passa a ser 4. O intervalo de 4 a 6 tem índice do meio 5, com valor 8. Agora nums[4] = 5 ≤ 8, a metade esquerda [5, 8] está ordenada e contém 5, então hi passa a ser 4. O índice 4 contém 5: retorne 4.
Como na busca binária simples, cada etapa reduz o intervalo pela metade, então o loop executa no máximo cerca de log2(n) + 1 vezes: 13 etapas para 5000 elementos, usando dois índices de memória extra.
Algoritmo
- Defina
lo = 0ehi = n-1. - Enquanto
lo ≤ hi, calculemid. Senums[mid]for igual atarget, retornemid. - Se
nums[lo] ≤ nums[mid], a metade esquerda está ordenada: senums[lo] ≤ target < nums[mid], definahi = mid - 1; caso contrário, definalo = mid + 1. - Caso contrário, a metade direita está ordenada: se
nums[mid] < target ≤ nums[hi], definalo = mid + 1; caso contrário, definahi = mid - 1. - Quando o loop terminar, retorne
-1.
def search(nums, target):
lo, hi = 0, len(nums) - 1 # target, if present, sits in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
# nums[lo..mid] is sorted: target is in it only if it fits its range
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# nums[mid..hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
Armadilhas e casos extremos
A busca em uma única passagem é curta, e quase todos os bugs estão em um operador de comparação.
- Escrever
nums[lo] < nums[mid]em vez de≤. Quando restam dois elementos,midé igual alo, e a metade esquerda tem um elemento, portanto está ordenada. Com o teste estrito,[9, 4]etarget = 4fazem com que[9, 4]seja tratada como a metade direita ordenada, procuram 4 fora do intervalo de 9 a 4 e retornam-1. - Comparar
targetcomnums[mid]primeiro, como na busca binária simples. Em[15, 19, 23, 2, 5, 8, 11]comtarget = 19, o valor do meio, 2, é menor que 19, então a busca segue para a direita e nunca encontra o índice 1. - Verificar apenas uma extremidade da metade ordenada. Em
[40, 50, 60, 70, 80, 10, 20]comtarget = 80, o valor do meio é 70, e a metade esquerda[40, 50, 60, 70]está ordenada. A verificaçãotarget ≥ nums[lo]sozinha direciona a busca para a esquerda, porque 80 é maior que 40, mas 80 também é maior que 70, então está na metade direita. Verifique as duas extremidades. - Esquecer o caso não rotacionado na abordagem de duas etapas. Quando
k = 0, a segunda execução é vazia, e seu intervalo vai de0a-1. Isso funciona com índices com sinal, mas com índices sem sinal (usizedo Rust),k - 1causa underflow, por isso o código Rust usa intervalos semiabertos. - Retornar a própria posição em Lua e R. As listas dessas linguagens começam em 1, então subtraia 1 antes de retornar.
Perguntas frequentes4
Qual é a complexidade de tempo da busca em um array ordenado e rotacionado?
Tempo O(log n) e espaço extra O(1). A cada etapa, mantém-se metade do intervalo atual, assim como na busca binária simples, então uma lista de 5000 elementos precisa de no máximo 13 etapas. A versão em duas etapas, que encontra primeiro o ponto de rotação, também é O(log n), com cerca do dobro de etapas.
Como você sabe qual metade de um array rotacionado está ordenada?
Compare nums[lo] com nums[mid]. Os valores diminuem apenas uma vez em toda a lista. Se nums[lo] ≤ nums[mid], essa queda não está entre lo e mid, então a metade esquerda está ordenada. Caso contrário, a queda está na metade esquerda, o que significa que a metade direita, de mid a hi, não tem nenhuma queda e está ordenada.
O algoritmo funciona quando o array contém duplicatas?
Não da forma como está escrito. Em [1, 0, 1, 1, 1], nums[lo], nums[mid] e nums[hi] são todos iguais a 1, então não é possível provar que nenhuma das metades está ordenada. A solução usual é avançar lo em uma posição quando nums[lo], nums[mid] e nums[hi] são iguais, o que mantém a resposta correta, mas faz com que o pior caso seja O(n).
Você deve encontrar primeiro o ponto de rotação ou pesquisar em uma única passagem?
Ambos executam em O(log n). Encontrar o índice do mínimo primeiro divide o problema em duas buscas binárias simples, então cada parte reutiliza um código em que você já confia. A busca em uma única passagem faz o mesmo trabalho em um único loop, com menos etapas, e é a versão que a maioria dos entrevistadores espera.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def search(nums, target):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
Esperado
4