Busca Binária

Cortar o problema pela metade

A busca linear percorre o array do começo ao fim até achar o valor. É O(n), funciona sempre e não exige nada da entrada. O problema aparece quando n cresce.

A busca binária troca uma exigência (o array precisa estar ordenado) por um poder: a cada olhada, metade dos candidatos é eliminada sem ser lida. Olhe o elemento do meio. Se ele é o alvo, acabou. Se é menor que o alvo, tudo o que está à esquerda dele também é menor, então some com essa metade inteira. Se é maior, some com a outra.

O que importa não é o que o algoritmo olha, é o que ele joga fora. Acompanhe a barra de candidatos encolhendo:

O número de passos é quantas vezes dá para dividir n por dois até sobrar 1, que é exatamente a definição de log₂:

Repare no formato da segunda coluna: multiplicar o array por mil não multiplica o trabalho por mil, acrescenta dez passos. É a mesma jogada que a árvore de busca binária faz em memória e que um índice de banco de dados faz em disco.

O contrato: sem ordem, não existe busca binária

A dedução "o alvo está à direita" só é válida porque tudo à esquerda do meio é comprovadamente menor. Num array desordenado essa frase vira um chute, e o algoritmo devolve a resposta errada com a mesma confiança. Não trava, não avisa: responde "não existe" sobre um valor que está lá.

O critério não precisa ser numérico nem crescente. Precisa ser total e consistente: strings em ordem alfabética, datas, decrescente, qualquer coisa que permita dizer "este vem antes daquele" sem ambiguidade.

Existe um segundo custo que costuma passar batido: manter o array ordenado enquanto ele recebe dados. Inserir na posição certa exige deslocar todo mundo depois dela, o que é O(n) por inserção. Se o seu caso é escrever muito e ler pouco, a busca binária sobre array pode ser a estrutura errada, e vale olhar tabelas hash (busca O(1) sem ordem) ou uma skip list.

O algoritmo, e as três decisões de cada passo

def busca_binaria(nums, alvo):
    esq, dir = 0, len(nums) - 1
    while esq <= dir:
        meio = esq + (dir - esq) // 2
        if nums[meio] == alvo:
            return meio
        if nums[meio] < alvo:
            esq = meio + 1
        else:
            dir = meio - 1
    return -1

São onze linhas e três detalhes que decidem se ele funciona.

O <= do laço. Com esq < dir, quando os dois ponteiros se encontram na mesma posição o laço encerra sem examinar aquele elemento, e um array de um elemento só nunca é olhado. O <= existe porque um intervalo de tamanho 1 ainda é um candidato legítimo.

O + 1 e o - 1. O elemento do meio já foi comparado e sabidamente não é o alvo, então ele tem que sair do intervalo. Escrever esq = meio em vez de esq = meio + 1 produz um laço infinito quando dir = esq + 1, porque o meio arredonda para baixo e cai sempre em esq.

A forma de calcular o meio. Essa merece uma seção inteira.

O bug do meio, que sobreviveu uma década no Java

A forma que todo mundo escreve primeiro é meio = (esq + dir) // 2. Ela está matematicamente certa e computacionalmente errada.

Num inteiro de 32 bits (o int de Java, C# e C, ou o int32 de Go), o maior valor representável é 2.147.483.647. Índices individuais cabem tranquilamente. A soma de dois índices grandes, não. Quando a soma passa do teto, o bit de sinal acende, o valor dá a volta e vira negativo, e o meio passa a apontar para fora do array.

Ajuste os dois ponteiros abaixo e veja os 32 bits acontecendo:

A correção é uma reescrita algébrica trivial: em vez de somar os dois e dividir, ache a distância entre eles, divida a distância e some ao ponto de partida.

meio = esq + (dir - esq) // 2      # a distância nunca estoura

Como dir - esq nunca é maior que dir, essa conta não tem como passar do teto. Mesma resposta, sem o risco, e custa exatamente o mesmo.

E antes de concluir que isso não te afeta: a defesa "meu array nunca terá 1 bilhão de posições" vale só enquanto esq e dir forem índices. Quando a busca binária passa a procurar sobre um espaço de respostas, os limites viram números do domínio do problema (uma capacidade, um prazo, um orçamento) e podem ser enormes desde a primeira linha. Use a fórmula segura sempre; não existe caso em que ela seja pior.

Quando não acha, a resposta ainda serve

Retornar -1 funciona, mas joga fora uma informação que o algoritmo já calculou de graça. Quando o laço termina sem achar, esq parou exatamente na posição onde o valor deveria ser inserido para o array continuar ordenado. Não é coincidência: o laço só termina quando o intervalo esvazia, e o único lugar em que isso pode acontecer é a fronteira entre os menores e os maiores que o alvo.

Isso resolve três problemas diferentes com o mesmo código e uma linha trocada:

• Onde entraria: nunca pare no acerto, deixe o laço ir até o fim e devolva esq.
• Primeira ocorrência: ao acertar, anote o índice e continue procurando para a esquerda.
• Última ocorrência: ao acertar, anote e continue para a direita.

As duas últimas são a resposta certa para arrays com repetidos, onde a busca de livro devolve uma ocorrência qualquer, dependendo de onde o meio caiu. Rodando as duas você tem o intervalo completo em 2 × O(log n), sem varrer os vizinhos um a um.

Sobre o valor de retorno, vale conhecer a convenção da biblioteca padrão: Arrays.binarySearch do Java e Array.BinarySearch do .NET devolvem -(ponto_de_inserção) - 1 quando falham. O sinal negativo diz "não achei" e o número carrega o ponto de inserção junto, então uma busca que falhou já entrega a inserção pronta. Multiplicar por -1 não serviria: -0 é 0, e a posição 0 ficaria indistinguível de um acerto. Em Python, o módulo bisect faz o mesmo trabalho com bisect_left e bisect_right.

Busca binária sem array

A parte que separa quem decorou o algoritmo de quem entendeu a ideia: a busca binária não precisa de um array. Ela precisa de duas coisas, e só:

Um exemplo concreto: dado um número n, ache o valor x tal que 1 + 2 + ... + x seja igual a x + (x+1) + ... + n. Para n = 8, a resposta é 6, porque 1+2+3+4+5+6 = 21 e 6+7+8 = 21.

Não existe array nenhum aqui, mas existe uma sequência ordenada implícita (1, 2, 3, ..., n) e uma soma que cresce sempre conforme x aumenta. Isso basta. E a soma de cada lado sai de uma fórmula fechada, a de Gauss, sem precisar de laço:

def soma_ate(x):
    return x * (x + 1) // 2          # 1 + 2 + ... + x, em O(1)

def acha_pivo(n):
    esq, dir = 1, n
    total = soma_ate(n)
    while esq <= dir:
        meio = esq + (dir - esq) // 2
        esquerda = soma_ate(meio)
        direita = total - soma_ate(meio - 1)
        if esquerda == direita:
            return meio
        if esquerda < direita:
            esq = meio + 1
        else:
            dir = meio - 1
    return -1

Repare no detalhe que estraga tudo se passar despercebido: se soma_ate fosse um laço em vez da fórmula de Gauss, cada passo custaria O(n) e o algoritmo inteiro viraria O(n log n), pior que a varredura O(n) que ele estava tentando substituir. Busca binária sobre um espaço de respostas só compensa quando o teste de cada passo é barato.

Essa ideia tem nome, binary search on the answer, e rende um tópico próprio: veja Busca Binária no Espaço de Respostas. A mesma lógica de dividir para conquistar também aparece na árvore de busca binária, onde o descarte de metade acontece escolhendo um ramo em vez de mexer em índices.

As armadilhas

O laço infinito. Se você escreveu esq = meio ou dir = meio sem o ajuste de 1, teste com um array de dois elementos. É onde ele trava, e é o teste que quase ninguém escreve.

Comparar com o vizinho em vez do alvo. Uma variante comum tenta detectar bordas olhando nums[meio - 1] ou nums[meio + 1] sem checar se esses índices existem. Prefira ajustar o intervalo e deixar o próprio laço convergir, como faz o visualizador de fronteira.

Confiar que a entrada está ordenada. Se o dado vem de fora, ou você garante a ordem no seu código, ou você tem um bug silencioso esperando. Em código crítico, uma verificação O(n) na entrada em ambiente de desenvolvimento custa pouco e evita muito.

Contar mal os passos. O pior caso é ⌊log₂ n⌋ + 1 comparações, não log₂ n. Com 8 elementos são 4, não 3. Um teste que espera 3 falha em uma entrada específica e passa nas outras.

Otimizar a busca esquecendo o resto. Achar um valor em O(log n) não ajuda se logo depois você inserir na posição encontrada: o deslocamento do array é O(n) e domina a soma. Ou o dado é majoritariamente estático, ou a estrutura precisa mudar.

Para consolidar, Big O tem um contador que roda busca binária e busca linear sobre o mesmo array lado a lado. E Two Pointers é a técnica vizinha mais próxima: também explora um array ordenado, também é O(n) ou melhor, e também morre se a ordem não existir.

Vídeo da aula

Direto do canal da comunidade Craft & Code Club · 1:30:11.

▶

Problemas para praticar

Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.

Referências

Artigos e materiais externos para se aprofundar.