Busca Binária
Divida para conquistar — elimine metade dos elementos a cada comparação.
O(log n)O(1)Como Funciona
Passo a passo do algoritmo
Receba a lista ordenada e o valor alvo
A busca binária só funciona em listas ordenadas. Ela precisa da lista e o valor que queremos encontrar.
função busca_binaria(lista_ordenada, alvo)Defina os limites: início e fim
Inicie com duas variáveis: low (índice 0) e high (último índice). Elas marcam o intervalo de busca.
low = 0, high = tamanho(lista) - 1Calcule o meio e compare
Encontre o índice do meio do intervalo atual e compare o elemento do meio com o alvo.
mid = (low + high) / 2; se lista[mid] == alvoAjuste o intervalo baseado na comparação
Se o elemento do meio for menor que o alvo, descarte a metade inferior (low = mid + 1). Se for maior, descarte a metade superior (high = mid - 1).
se lista[mid] < alvo: low = mid + 1; senão: high = mid - 1Repita até encontrar ou esgotar
Continue dividindo o intervalo ao meio até encontrar o elemento ou até low ultrapassar high, indicando que o elemento não existe.
enquanto low <= high; retorne -1 se não encontrarImplementação
Código comentado em JavaScript e Python
function buscaBinaria(lista, alvo) {
let low = 0;
let high = lista.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
const chute = lista[mid];
if (chute === alvo) {
return mid; // encontrou!
}
if (chute > alvo) {
high = mid - 1; // alvo está na metade inferior
} else {
low = mid + 1; // alvo está na metade superior
}
}
return -1; // não encontrou
}
// Exemplo de uso (lista DEVE estar ordenada)
const numeros = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const resultado = buscaBinaria(numeros, 7);
console.log(resultado); // 3Playground
Visualize o algoritmo em ação
Quando Usar
Cenários ideais para este algoritmo
Listas ordenadas grandes
Quando você tem milhares ou milhões de elementos ordenados, a busca binária é drasticamente mais rápida que a busca simples.
Dicionários e enciclopédias
Procurar palavras em ordem alfabética é o exemplo clássico — você não lê página por página, mas sim abre no meio e decide para qual lado ir.
Buscas repetidas
Se você vai buscar muitas vezes no mesmo dataset, vale a pena ordenar uma vez e usar busca binária nas buscas subsequentes.
Dados já indexados
Sistemas com índices ordenados (databases, bibliotecas) usam variações da busca binária para localizar registros rapidamente.
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Melhor caso | O(1) |
| Caso médio | O(log n) |
| Pior caso | O(log n) |