Busca binária: cortar pela metade

O jogo de adivinhar o número

Você provavelmente já jogou a versão humana da busca binária. Alguém pensa num número de 1 a 100 e você tenta adivinhar; a cada palpite, a pessoa diz se o número é maior ou menor. O jeito esperto de jogar não é chutar 1, 2, 3; é chutar 50. Se a pessoa diz maior, você descarta de 1 a 50 e sabe que está entre 51 e 100. Chuta 75, e assim por diante, sempre no meio do que sobrou. Com essa estratégia, você acerta qualquer número de 1 a 100 em no máximo sete tentativas, porque cada palpite corta as possibilidades pela metade. A busca binária numa lista ordenada é exatamente isso: o item do meio é o seu palpite, e a comparação com o alvo diz para qual metade ir.

lista <- [4, 8, 15, 16, 23, 42]   // ORDENADA
alvo <- 23
inicio <- 0
fim <- 5
enquanto inicio <= fim faça
  meio <- (inicio + fim) / 2   // parte inteira
  se lista[meio] = alvo então
    escreva("Achei na posição ", meio)
    interrompa
  senão se lista[meio] < alvo então
    inicio <- meio + 1   // descarta a metade de baixo
  senão
    fim <- meio - 1      // descarta a metade de cima
  fim
fim

A faixa (início, fim) encolhe pela metade a cada passo, movendo o início ou o fim conforme a comparação com o meio.

A busca binária passo a passo

Vamos seguir a busca pelo 23 na lista ordenada [4, 8, 15, 16, 23, 42], com posições de 0 a 5. A faixa começa inteira: início 0, fim 5, meio na posição 2 (o valor 15). Comparo: 15 é menor que 23, então o alvo está à direita; movo o início para depois do meio, virando início 3, fim 5. Nova faixa, novo meio na posição 4 (o valor 23). Comparo: 23 é igual ao alvo, achei, na posição 4. Foram duas comparações para achar um item numa lista de seis. Numa busca linear, o 23 estaria na quinta posição e custaria cinco comparações. A vantagem parece pequena aqui, mas ela explode com o tamanho: é isso que a próxima aula revela em números.

lista <- [2, 5, 8, 12, 20]   // posições 0 a 4
// busca binária pelo 5
// primeiro passo: meio = (0 + 4) / 2 = 2

A condição inegociável e os cuidados

A busca binária tem uma exigência que não se negocia: os dados precisam estar ordenados. Aplicada a uma lista embaralhada, ela dá respostas erradas, porque a comparação com o meio deixa de indicar de que lado está o alvo. Esse é o preço da velocidade: você troca a universalidade da busca linear pela exigência da ordem. Além disso, escrever a busca binária pede cuidado com os detalhes, mover o início para meio mais um, o fim para meio menos um, e a condição de parada do laço, porque um deslize de uma unidade vira laço infinito ou item não encontrado por engano. Vale escrevê-la com calma, testar as pontas (o primeiro item, o último, um que não existe) e conferir com o teste de mesa. Nas linguagens reais, quase sempre existe uma busca binária pronta e testada, mas entender como ela funciona por dentro é o que faz você saber quando pode confiar nela.