Binary Search
Você recebe uma lista de inteiros nums ordenada em ordem crescente, sem valores repetidos, e um inteiro target. Retorne o índice de target em nums, começando a contar do 0, ou -1 se ele não estiver na lista. Busque um tempo de O(log n), o que significa que você não pode se dar ao luxo de verificar cada elemento.
Função
- numsinteger-array
- a lista ordenada de números inteiros distintos
- targetinteger
- o valor a ser procurado
- Retornainteger
- o índice de target em nums, ou -1 se ele não estiver presente
Restrições
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsestá ordenado em ordem estritamente crescente, então cada valor aparece uma vez.
Exemplos
- Entrada
- nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
- Saída
- 4
- Explicação
nums[4]é 9. A busca verifica o índice 3 (valor 4, pequeno demais), depois o índice 5 (valor 15, grande demais) e, em seguida, o índice 4, onde encontra 9.
- Entrada
- nums = [1, 3, 5, 8, 13, 21]target = 10
- Saída
- -1
- Explicação
- 10 ficaria entre 8 e 13, e nenhum dos dois é 10, então ele não está na lista. O intervalo de busca diminui até que
loultrapassehi, e a função retorna-1.
+15 testes ocultos ao enviar
Para ir além
Se nums pudesse ter valores repetidos, como você retornaria o primeiro índice de target, ainda em O(log n)?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
A lista está ordenada. Se você comparar
targetcom um elemento no meio, o que isso informa sobre todos os elementos de um dos lados dele?Se
nums[mid] < target, entãonums[mid]e tudo à sua esquerda são pequenos demais, entãotargetsó pode estar à direita. Uma comparação elimina metade dos candidatos.Mantenha dois índices,
loehi, delimitando a parte da lista que ainda pode contertarget. Compare com o elemento do meio, movaloouhipara além dele e pare quando encontrartargetou quandoloultrapassarhi.
Solução
Ler os elementos um por um encontra target, mas ignora o fato que torna o problema interessante: a lista está ordenada. Uma única comparação com o elemento do meio informa qual metade ainda pode conter target, então você pode descartar metade dos candidatos a cada etapa. Uma lista com 10^4 elementos precisa, então, de no máximo 14 comparações, em vez de 10000.
Examine da esquerda para a direita
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, target não está na lista, então retorne -1. Cada elemento é comparado uma vez, o que torna a resposta correta para qualquer lista, ordenada ou não.
Essa generalidade é o problema. Uma lista com 10^4 elementos custa até 10000 comparações, e o trabalho cresce proporcionalmente a n. A varredura nunca usa o fato de que nums está ordenada, então não atinge o limite O(log n) solicitado pela tarefa. Você poderia parar mais cedo assim que um valor ultrapassasse target, mas, no pior caso, ainda leria a lista inteira.
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 -1Busca binária com dois índices
Intuição
Mantenha dois índices, lo e hi, com uma garantia: se target estiver na lista, seu índice estará entre lo e hi, inclusive. No início, esse intervalo corresponde à lista inteira, de 0 a n-1. Observe o índice do meio, mid. Se nums[mid] for igual a target, você terminou. Se for menor, então, como a lista está ordenada, todos os elementos até mid também são menores, então mova lo para mid + 1. Se for maior, mova hi para mid - 1. A garantia continua válida após qualquer um dos movimentos.
Acompanhe o primeiro exemplo: [-7, -2, 0, 4, 9, 15, 23] com target = 9. O intervalo de 0 a 6 tem o índice do meio igual a 3, com valor 4, que é pequeno demais, então o intervalo passa a ser de 4 a 6. Seu índice do meio é 5, que contém 15, grande demais, então o intervalo passa a ser de 4 a 4. O índice 4 contém 9: retorne 4.
Se target não estiver presente, o intervalo continuará diminuindo até que lo ultrapasse hi. O intervalo estará vazio; a garantia indica que target não está em lugar nenhum, e você retorna -1. Cada etapa reduz o intervalo pela metade, então o loop é executado no máximo cerca de log2(n) + 1 vezes: 14 etapas para 10^4 elementos. Dois índices são toda a memória extra de que você precisa.
Algoritmo
- Defina
lo = 0ehi = n-1. - Enquanto
lo ≤ hi, calculemid = lo + (hi - lo) / 2. - Se
nums[mid]for igual atarget, retornemid. - Se
nums[mid] < target, 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[mid] < target:
lo = mid + 1 # nums[mid] and everything left of it is too small
else:
hi = mid - 1 # nums[mid] and everything right of it is too big
return -1
Armadilhas e casos extremos
A busca binária é curta, e quase todo bug é um erro de uma posição nas extremidades do intervalo.
- Usar o laço com
lo < hienquantohicomeça no último índice. O laço termina enquanto ainda há um candidato não verificado, entãonums = [5]comtarget = 5retorna-1. Com um intervalo inclusivo, use o laço enquantolo ≤ hi. - Avançar para
lo = midouhi = midcom um intervalo inclusivo. Quandoloehisão vizinhos,midé igual aloe o intervalo nunca diminui: um laço infinito. Você já verificounums[mid], então avance além dele usandomid + 1oumid - 1. - Calcular
(lo + hi) / 2usando um inteiro de largura fixa. A soma transborda quando os índices passam de aproximadamente10^9. Os limites aqui estão muito abaixo disso, maslo + (hi - lo) / 2é o hábito seguro. - Retornar
loquandotargetnão for encontrado. Depois do laço,loé o ponto de inserção, que é um índice válido, não-1. - Esquecer o deslocamento em Lua e R. As listas dessas linguagens começam em 1, então o índice que você retorna é a posição menos 1.
Perguntas frequentes4
Qual é a complexidade de tempo da busca binária?
O(log n). Cada comparação reduz pela metade o intervalo que ainda pode conter o alvo, então, após k etapas, restam no máximo n / 2^k candidatos. Uma lista de 10^4 elementos precisa de no máximo 14 comparações, e uma lista de 10^9 elementos, de no máximo 30. A versão iterativa usa O(1) de espaço extra.
Por que a busca binária precisa de um array ordenado?
A etapa que descarta metade da lista depende da ordenação. Quando nums[mid] < target, a ordenação garante que todo elemento à esquerda de mid também é menor que target, então nenhum deles pode corresponder. Em uma lista não ordenada, essa comparação não diz nada sobre os outros elementos, e você precisa verificar todos eles.
É melhor que a busca binária seja iterativa ou recursiva?
Ambas estão corretas e ambas são executadas em tempo O(log n). A versão recursiva chama a si mesma em uma das metades e usa espaço de pilha O(log n); a versão iterativa move lo e hi em um loop e usa O(1). Em geral, os entrevistadores esperam o loop, que evita qualquer limite de recursão.
Como evitar overflow ao calcular o índice do meio?
Escreva mid = lo + (hi - lo) / 2 em vez de (lo + hi) / 2. Ambas as formas dão o mesmo índice, mas a segunda forma soma dois índices primeiro e, em um inteiro de 32 bits, essa soma transborda quando os índices passam de aproximadamente 1.07 × 10^9. Python e Ruby têm inteiros ilimitados, então, nesses casos, a forma curta é segura.
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
Entrada
nums = [-7, -2, 0, 4, 9, 15, 23] target = 9
Esperado
4