24 de Março
Busca binária
Como usar a ordenação para eliminar metade do espaco de busca e manter um invariante claro.
Busca Iniciante 15 min TypeScript
Dado um array de inteiros nums ordenado em ordem crescente e um inteiro target, retorne o indice de target se ele existir. Caso contrario, retorne -1.
Exemplo:
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
O que perceber antes de codar
- O array esta ordenado. Essa e a informação mais importante do problema.
- Cada comparação com o meio elimina metade do espaco ainda possível.
- Quando o alvo não existe, a busca precisa terminar em `-1`.
Erros comuns
- usar atualização de limites errada e criar loop infinito
- usar `left < right` sem entender que pode perder a ultima posição candidata
Passo 1 — Escrever o que você faria sem a ordenação
Sem array ordenado, a versão inicial seria simples: olhar um por um.
Isso já ajuda a enxergar o valor da ordenação.
O ganho da busca binaria não e "andar mais rápido".
O ganho e:
eliminar metade das possibilidades a cada passo.
Passo 2 — Escrever a versão inicial correta
A versão mais direta e busca linear:
export function search(nums: number[], target: number): number {
for (let index = 0; index < nums.length; index += 1) {
if (nums[index] === target) {
return index
}
}
return -1
}
Funciona, mas ignora a melhor pista do enunciado.
Passo 3 — Perguntar o que o meio te diz
Se você olha nums[mid]:
- se for igual ao target, acabou
- se for menor, toda a metade esquerda vira impossivel
- se for maior, toda a metade direita vira impossivel
Essa palavra "impossivel" e o centro do algoritmo.
Passo 4 — Manter um intervalo ainda valido
Use dois limites:
left: primeira posição ainda possívelright: ultima posição ainda possível
Enquanto left <= right, existe pelo menos uma candidata.
Quando o meio falha, descarte a metade impossivel ajustando os limites.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function search(nums: number[], target: number): number {
// sua solução aqui
return -1
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(log n)
Espaço: O(1)
Solução 1 — Busca linear O(n)
Funciona, mas não usa a ordenação.
export function search(nums: number[], target: number): number {
for (let index = 0; index < nums.length; index += 1) {
if (nums[index] === target) {
return index
}
}
return -1
}Solução 2 — Busca binaria O(log n)
Agora a ordenação vira eliminacao real de espaco de busca.
export function search(nums: number[], target: number): number {
let left = 0
let right = nums.length - 1
while (left <= right) {
const mid = Math.floor((left + right) / 2)
const value = nums[mid]
if (value === target) {
return mid
}
if (value < target) {
left = mid + 1
continue
}
right = mid - 1
}
return -1
}O importante aqui não e decorar o loop. E manter o intervalo de candidatos coerente.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial linear custa
O(n). Como o array esta ordenado, cada comparação com o meio me permite eliminar metade do intervalo ainda possível. Eu mantenho[left, right]como conjunto de indices candidatos e ajusto os limites até achar o alvo ou esgotar o intervalo.
Isso mostra que você:
- usou a informação certa do enunciado
- explicou o algoritmo como invariante
- reduziu a chance de errar bounds por simples decoração
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- procurar em espaco ordenado
- eliminar metade das possibilidades
- manter limites validos
- justificar por que uma região inteira ficou impossivel
O ponto não e decorar busca binaria.
O ponto e aprender a raciocinar em termos de intervalo candidato.