Pesquisa binária

A pesquisa binária é a forma como procura uma palavra num dicionário: abre-o a meio, vê se a palavra vem antes ou depois e repete com essa metade. Numa lista ordenada, encontra qualquer valor entre um milhão em, no máximo, 20 comparações.

Uma fila ordenada de barras com a barra do meio destacada, metade da fila esbatida e uma linha tracejada à altura do alvo
Uma fila ordenada de barras com a barra do meio destacada, metade da fila esbatida e uma linha tracejada à altura do alvo

A ideia

Numa lista ordenada, uma comparação diz-lhe mais do que se encontrou o alvo: diz-lhe de que lado ele está. Compare o alvo com o valor do meio. Se forem iguais, terminou. Se o valor do meio for menor, tudo o que está antes dele também é menor, por isso o alvo só pode estar depois. Se for maior, o alvo só pode estar antes. Fique só com essa metade e repita.

Um exemplo

Procure 23 em 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. O valor do meio é 16, que é menor, por isso só restam 23 a 91. O meio destes é 56, que é maior, por isso só restam 23 e 38. O meio destes é 23: encontrado na posição 6 após 3 comparações, quando a pesquisa linear precisa de 6. Procurar 40 na mesma lista compara 16, 56, 23 e 38, e depois não resta nada: 4 comparações para saber que 40 não está lá, contra 10 da pesquisa linear.

Dividir ao meio rende depressa

Após uma comparação resta, no máximo, metade da lista, após duas um quarto, após k no máximo cerca de n/2ᵏ. A pesquisa para quando não resta nada, por isso precisa, no máximo, de ⌊log₂ n⌋ + 1 comparações: 6 para 40 valores, 10 para 1000, 20 para um milhão e 30 para mil milhões. Duplicar a lista acrescenta apenas uma comparação. Escreve-se O(log n).

Fácil de descrever, difícil de acertar

John Mauchly descreveu a pesquisa binária em 1946, mas, segundo Donald Knuth, a primeira versão que funcionava para qualquer comprimento de lista só foi publicada em 1962. Mais tarde, Jon Bentley verificou que só cerca de um em cada dez programadores profissionais a escrevia corretamente: as condições de paragem e o mais ou menos um ao cortar as metades são fáceis de errar. Em 2006, Joshua Bloch mostrou que a forma habitual de encontrar o meio, (low + high) / 2, pode causar overflow em listas muito longas, um erro que esteve anos na biblioteca do Java. Escrever low + (high − low) / 2, como faz a aplicação, evita-o.

John Mauchly (quinto a partir da esquerda) com outros responsáveis do ENIAC diante da máquina, numa fotografia do Exército dos Estados Unidos. Mauchly descreveu a pesquisa binária em 1946.
John Mauchly (quinto a partir da esquerda) com outros responsáveis do ENIAC diante da máquina, numa fotografia do Exército dos Estados Unidos. Mauchly descreveu a pesquisa binária em 1946.

Variantes e usos

Com duplicados, a pesquisa binária encontra uma das correspondências; as versões que continuam para a esquerda ou para a direita encontram a primeira ou a última, ou a posição onde um valor em falta seria inserido. A mesma ideia de dividir ao meio encontra a raiz de uma equação (bisseção), a versão em que um erro apareceu pela primeira vez (git bisect) e a resposta a muitos problemas de otimização. As árvores binárias de pesquisa guardam os dados de forma que cada consulta siga o mesmo caminho de divisões ao meio.

Explore

Abra a aplicação, escolha um valor em Procurar e prima Avançar. A parte sombreada é onde o alvo ainda pode estar; o valor do meio fica destacado, e a metade excluída esbate-se. Os contadores mostram quantos valores ainda são possíveis e de quantas comparações uma pesquisa linear precisaria para o mesmo valor. Procure um valor em falta, ou use 40 barras, para ver a diferença crescer.

Perguntas frequentes

Qual é a complexidade temporal da pesquisa binária?

O(log n): no máximo ⌊log₂ n⌋ + 1 comparações para n valores. No melhor caso, basta uma comparação, quando o alvo está no meio. A versão iterativa precisa de O(1) de memória extra.

Qual é a diferença entre pesquisa binária e pesquisa linear?

A pesquisa linear verifica cada valor à vez e funciona com qualquer lista, mas pode precisar de n comparações. A pesquisa binária só funciona com uma lista ordenada, mas exclui metade do que resta em cada comparação, por isso precisa de cerca de log₂ n.

Vale a pena ordenar uma lista só para usar a pesquisa binária?

Só se pesquisar nela muitas vezes. Ordenar custa cerca de n log n passos, mais do que uma única pesquisa linear. Depois de a lista estar ordenada, cada pesquisa seguinte é muito barata.

A pesquisa binária funciona com outras coisas além de listas?

Sim, com tudo em que um teste lhe diga de que lado da resposta está: um intervalo de números, as versões de um programa ou os palpites num jogo de maior ou menor.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar a pesquisa binária