Pesquisa binária
Encontra um valor num vetor ordenado olhando para o meio e descartando a metade onde não pode estar. Cada comparação corta para metade o que resta.
- melhor caso Ω(1)
- caso médio Θ(log n)
- pior caso O(log n)
- memória O(1)
O que significam estes termos?
- Ordenado: por ordem crescente. A pesquisa binária precisa disso; com dados desordenados dá respostas erradas.
- Cortar para metade: cada comparação descarta metade do que resta, a metade onde o alvo não pode estar.
- log₂ n: quantas vezes se pode dividir n por 2 até restar 1. Para 64 valores são 6, logo no máximo 7 comparações.
- meio (mid)
- encontrado
- descartado
- alvo
Cada meio que a pesquisa 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: saltar.
Experimente: Escolha um alvo que não esteja no vetor. A pesquisa termina na mesma após no máximo ⌈log₂(n + 1)⌉ comparações, quando lo ultrapassa hi.
Como funciona
A pesquisa binária mantém duas marcas, lo e hi, à volta da parte do vetor onde o alvo ainda pode estar. Olha para o valor do meio: se for o alvo, acabou; se for menor, o alvo só pode estar à direita, por isso lo passa para depois do meio; se for maior, hi passa para antes. Cada passo corta o resto para metade: 64 valores exigem no máximo 7 comparações e um milhão no máximo 20. Quando lo ultrapassa hi, não resta nada: o valor não está no vetor.
Quando é uma boa escolha
Use a pesquisa binária sempre que os dados estejam ordenados e se possa 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. Com dados desordenados dá respostas erradas, e ordenar antes só compensa se pesquisar muitas vezes.