A busca binária (ou pesquisa binária) encontra um valor em um vetor ordenado descartando metade dos elementos a cada comparação. A animação mostra os índices de início, fim e meio em cada passo e compara com o número de comparações da busca linear.
Busca Binária em C
int busca_binaria(int v[], int n, int alvo) {
int inicio = 0, fim = n - 1;
while (inicio <= fim) {
int meio = inicio + (fim - inicio) / 2;
if (v[meio] == alvo) return meio;
if (v[meio] < alvo) inicio = meio + 1;
else fim = meio - 1;
}
return -1; /* não encontrado */
}Busca Binária em Python
def busca_binaria(v, alvo):
inicio, fim = 0, len(v) - 1
while inicio <= fim:
meio = (inicio + fim) // 2
if v[meio] == alvo:
return meio
if v[meio] < alvo:
inicio = meio + 1
else:
fim = meio - 1
return -1
# Na biblioteca padrão:
import bisect
bisect.bisect_left(v, alvo)Busca Binária em Java
static int buscaBinaria(int[] v, int alvo) {
int inicio = 0, fim = v.length - 1;
while (inicio <= fim) {
int meio = inicio + (fim - inicio) / 2;
if (v[meio] == alvo) return meio;
if (v[meio] < alvo) inicio = meio + 1;
else fim = meio - 1;
}
return -1;
}
// ou: Arrays.binarySearch(v, alvo);Versão Recursiva
def busca(v, alvo, inicio, fim):
if inicio > fim:
return -1
meio = (inicio + fim) // 2
if v[meio] == alvo:
return meio
if v[meio] < alvo:
return busca(v, alvo, meio + 1, fim)
return busca(v, alvo, inicio, meio - 1)Perguntas Frequentes
Como funciona a busca binária?
Em um vetor ordenado, compare o elemento do meio com o valor procurado. Se for igual, achou. Se o procurado for maior, descarte a metade esquerda; se for menor, descarte a direita. Repita na metade que sobrou até achar ou o intervalo ficar vazio.
Qual a complexidade da busca binária?
O(log n). A cada comparação o intervalo cai pela metade, então um vetor de 1 milhão de elementos precisa de no máximo 20 comparações, e um de 1 bilhão, no máximo 30. A busca linear precisaria de até n comparações.
A busca binária funciona em vetor desordenado?
Não. Ela depende de o vetor estar ordenado para saber qual metade descartar. Se a lista não está ordenada, é preciso ordenar antes (O(n log n)) ou usar busca linear.
Qual o bug clássico da busca binária?
Calcular o meio como (inicio + fim) / 2 pode estourar o limite de inteiros em C e Java quando os índices são muito grandes. A forma segura é inicio + (fim − inicio) / 2. Esse bug ficou anos na biblioteca padrão do Java até ser corrigido em 2006.