Busca Binária: Eficiência Logarítmica
O salto de performance da busca sequencial para a busca binária.
Busca Sequencial (2.3)
Verifica um por um. Em uma lista de 1.000.000 de itens, o pior caso exige 1.000.000 de comparações.
Complexidade: O(n)
Busca Binária (2.10)
Divide a lista ao meio a cada passo. No mesmo milhão de itens, exige no máximo 20 comparações.
Complexidade: O(log n)
O Pré-requisito Fundamental
Diferente da busca sequencial, a busca binária exige que a lista esteja ordenada. Sem ordenação, a lógica de descartar metades é impossível. Na engenharia, ordenamos dados uma vez para buscá-los milhares de vezes com alta performance.
Raciocínio de Desenvolvimento
1. Definir Limites
Esquerda e Direita
Marcamos o início (0) e o fim (n-1) do vetor de dados.
2. Calcular o Meio
Ponto de Divisão
Calculamos m = (esq + dir) // 2 para testar o elemento central.
3. Comparar e Descartar
Redução do Espaço
Se o alvo é menor que o meio, descartamos a metade direita. Se maior, descartamos a esquerda.
def busca_binaria(L, x):
inicio = 0
fim = len(L) - 1
while inicio <= fim:
meio = (inicio + fim) // 2
if (L[meio] == x):
return meio # Encontrado!
elif (L[meio] < x):
inicio = meio + 1 # Busca na direita
else:
fim = meio - 1 # Busca na esquerda
return -1 # Não encontrado
Simulador "Dividir para Conquistar"
Observe como metade da memória é descartada a cada comparação.