Busca binária
Encontra um valor num vetor ordenado olhando o meio e descartando a metade onde ele não pode estar. Cada comparação corta pela metade o que sobra.
- melhor caso Ω(1)
- caso médio Θ(log n)
- pior caso O(log n)
- memória O(1)
O que significam esses termos?
- Ordenado: em ordem crescente. A busca binária precisa disso; em dados desordenados ela dá respostas erradas.
- Cortar pela metade: cada comparação descarta metade do que sobra, a metade onde o alvo não pode estar.
- log₂ n: quantas vezes dá para dividir n por 2 até sobrar 1. Para 64 valores são 6, então no máximo 7 comparações.
- meio (mid)
- encontrado
- descartado
- alvo
Cada meio que a busca poderia escolher; uma execução é um caminho para baixo. Níveis: 5 = ⌈log₂(24 + 1)⌉, o máximo de comparações necessárias.
Procuro 70 entre 24 valores ordenados: o vetor inteiro ainda está em jogo.
Espaço: reproduzir ou pausar. Setas esquerda e direita: avançar passo a passo. Home e End: pular.
Experimente: Escolha um alvo que não esteja no vetor. A busca ainda termina após no máximo ⌈log₂(n + 1)⌉ comparações, quando lo passa de hi.
Como funciona
A busca binária mantém duas marcas, lo e hi, em volta da parte do vetor onde o alvo ainda pode estar. Ela olha o valor do meio: se for o alvo, acabou; se for menor, o alvo só pode estar à direita, então lo passa para depois do meio; se for maior, hi passa para antes. Cada passo corta o resto pela metade: 64 valores exigem no máximo 7 comparações e um milhão no máximo 20. Quando lo passa de hi, não sobra nada: o valor não está no vetor.
Quando é uma boa escolha
Use busca binária sempre que os dados estiverem ordenados e você puder saltar para qualquer posição: uma palavra numa lista ordenada, uma versão num histórico, git bisect, o ponto de inserção num vetor ordenado. Em dados desordenados ela dá respostas erradas, e ordenar antes só compensa se você buscar muitas vezes.