Lições Interativas de Matemática e Ciências

← Computação

Pesquisa binária: quatro escolhas, dezasseis ciclos

Escolha as quatro partes do código: a condição do ciclo, o valor inicial de hi e as duas atualizações. Ao lado, pode acompanhar a execução num pequeno vetor ordenado, uma iteração de cada vez. O veredito testa todos os vetores até ao comprimento indicado e todos os valores procurados; o primeiro caso de falha fica a um clique.

A carregar a simulação interativa...

Lição

A teoria — Pesquisa binária: quatro escolhas, dezasseis ciclos

A pesquisa binária encontra um valor x num vetor ordenado mantendo um intervalo de índices, de lo a hi, que terá de conter x se este estiver presente. Em cada iteração, lê o elemento central, a[mid], e conserva a metade onde x pode estar. O intervalo é fechado quando hi é o último índice ainda incluído (lo <= hi, com hi a começar em n − 1) e semiaberto quando hi é o primeiro índice posterior ao intervalo (lo < hi, com hi a começar em n).

O que significa cada símbolo

lo, hi
os extremos do intervalo ainda por pesquisar
mid
⌊(lo + hi)/2⌋, o índice lido nesta iteração
n
o número de elementos, nos índices de 0 a n − 1
N
o comprimento do maior vetor testado pelo veredito: todos os n de 0 a N e todos os valores procurados, num total de (N + 1)² casos
Pressupõe
Os valores do vetor são distintos, o ciclo devolve o resultado assim que a[mid] é igual a x e, na execução e no veredito, os inteiros não têm limite superior. A tabela de excesso de capacidade abandona esta última hipótese e efetua os cálculos em 32 bits, como Java.
Falha quando
Com valores repetidos, os dois ciclos corretos continuam a devolver um índice que contém x, mas não necessariamente o primeiro. Para encontrar a primeira ocorrência, como exige uma consulta por intervalo num índice ordenado, é preciso um ciclo que não pare quando encontra uma igualdade: um intervalo semiaberto, hi = mid sempre que a[mid] ≥ x, sendo lo a resposta quando o ciclo termina.

Catorze dos dezasseis ciclos estão errados, e dois elementos bastam para o provar 🖖

Cada uma das quatro escolhas no código exige atenção, embora as duas opções pareçam razoáveis. A tabela sob os resultados executa os dezasseis ciclos em todos os vetores até 12 elementos e para todos os valores procurados: 169 casos. Dois ciclos passam. Todos os outros falham num vetor com, no máximo, dois elementos; treze dos catorze falham num vetor com um elemento ou no vetor vazio. Limite o teste a 1 elemento e sobrevivem três ciclos; com 2, restam apenas os dois corretos; com 256, nenhum primeiro caso de falha muda. Estes casos pequenos constituem um teste completo, não uma amostra, porque o ciclo só usa cada valor para o comparar com x. Qualquer vetor ordenado com n números distintos comporta-se como 1, 3, 5 …, com o valor procurado numa das suas 2n + 1 posições possíveis, sobre um elemento ou numa lacuna. O veredito experimenta todas elas. Em Programming Pearls, Jon Bentley resume a dificuldade com duas datas: "Embora a primeira pesquisa binária tenha sido publicada em 1946, a primeira que funciona corretamente para todos os valores de n só apareceu em 1962."

Os dois ciclos quase corretos falham, cada um, para no máximo um valor por vetor 🖖

Prima Falha o último. Com lo < hi e hi = n − 1, o ciclo termina quando lo encontra hi, sem ler o elemento dessa posição. Cada atualização mantém x dentro do intervalo, e mid nunca coincide com hi. Assim, o único elemento que pode ficar por ler é aquele onde hi começa: o ciclo encontra todos os elementos de todos os vetores, exceto o último. Prima Lê para lá do fim para ver a imagem simétrica. Com hi = n e lo <= hi, a[n] pertence ao intervalo, e apenas um valor maior do que todos os elementos conduz lo até lá. Até 256 elementos, os dois ciclos erram 256 e 257 dos 66.049 casos. Só no vetor de 256 elementos, falham em 0,19% dos valores procurados, pelo que cem valores escolhidos ao acaso nesse vetor não costumariam revelar nenhum dos erros. O vetor vazio apanha o segundo ciclo no seu único caso; um vetor com um elemento apanha o primeiro. Em JavaScript, o segundo ciclo chega a escapar: a[n] é undefined, ambas as comparações são falsas, e o ciclo define hi = mid − 1 e responde −1, corretamente. Em Java, a mesma leitura lança uma exceção; em C, o comportamento é indefinido.

O ciclo correto do JDK falhou acima de 230 elementos 🖖

O ciclo do JDK ocupa a primeira linha da tabela, acerta em todos os casos que o veredito consegue testar e foi escrito por Joshua Bloch para java.util.Arrays. Em Java, lo + hi é um int de 32 bits; acima de 2.147.483.647, dá a volta e torna-se negativo. Num relatório de erro enviado à Sun em 11 de maio de 2004, uma pesquisa pelo último elemento de um vetor com 1.100.000.000 bytes produziu ArrayIndexOutOfBoundsException: -1064671149. A tabela de excesso de capacidade repete essa pesquisa sem reservar memória: no passo 6, lo + hi vale 2.165.624.999 e, depois da volta e do deslocamento, o ponto médio é −1.064.671.149, exatamente o número do relatório. No mesmo passo, lo + ((hi − lo) >> 1) dá 1.082.812.499. O título do relatório afirma que a pesquisa falha em vetores maiores do que 1<<30, com toda a precisão: introduza 1.073.741.824 e o maior lo + hi será 231 − 2, que ainda cabe; acrescente um elemento e a pesquisa excederá a capacidade no passo 31. Num texto de 2006 sobre o erro, Bloch conta que este ficou à espera "durante cerca de nove anos" e observa que a versão do próprio Bentley em Programming Pearls, aí demonstrada como correta, sofre do mesmo problema. A frase de Bentley, "define m como a média de l e u, truncada para o inteiro imediatamente inferior", é verdadeira para os inteiros e falsa para inteiros de 32 bits.

Problema resolvido na íntegra

  1. Porque só restam dois ciclos 4 passos

    Carregue em Preso em lo = mid. O verificador só consegue testar vetores com até 256 elementos. Demonstre, para qualquer n, que o ciclo semiaberto com lo = mid + 1 termina sempre, que o mesmo ciclo com lo = mid fica preso quando hi = lo + 1 e a[lo] < x, e determine o que este raciocínio exige do ciclo fechado.

    Abrir este problema na ferramenta

    1. No ciclo semiaberto, o corpo só é executado enquanto lo < hi. Como mid é arredondado para baixo, é pelo menos igual a lo e estritamente menor do que hi.

    2. Assim, hi = mid reduz hi em pelo menos uma unidade, enquanto lo = mid + 1 aumenta lo em pelo menos uma unidade. Em ambos os casos, hi − lo começa em n e diminui pelo menos uma unidade a cada passagem. Como não pode ficar abaixo de zero, o ciclo termina em no máximo n passagens.

    3. Considere agora lo = mid. Quando hi = lo + 1, mid é ⌊(2lo + 1)/2⌋ = lo. Se a[lo] < x, a atualização não altera lo, e a passagem seguinte repete exatamente a anterior. O exemplo predefinido chega a esse ponto com lo = 6, hi = 7, a[6] = 13 e x = 14.

    4. O ciclo fechado é executado enquanto lo <= hi, portanto admite lo = hi. Nesse caso, mid = lo = hi: uma atualização para mid não altera nada, logo ambas as atualizações têm de ultrapassar mid. Podem fazê-lo porque a[mid] acabou de ser lido. O intervalo semiaberto já exclui hi; nesse ciclo, hi = mid elimina o elemento acabado de ler e todos os que estão acima dele, pois a[mid] > x exclui-os. Já hi = mid − 1 eliminaria também a[mid − 1], que pode ser x.

    Resposta

    Cada passagem tem de reduzir o intervalo, eliminar apenas índices que não podem conter x e partir de um intervalo que abranja todo o vetor. Para lo <= hi, isso exige hi = n − 1, hi = mid − 1 e lo = mid + 1; para lo < hi, exige hi = n, hi = mid e lo = mid + 1. O verificador confirma estes dois ciclos até 256 elementos, mas o argumento é válido para qualquer n, coisa que nenhum teste consegue provar. Com aritmética de 32 bits, falta ainda supor que lo + hi cabe no tipo usado. A terceira observação mostra o que acontece quando essa condição não se verifica.

Percurso de aprendizagem

Por que razão um algoritmo está correto

Referências (2)

· Verificado com fontes publicadas. Correções bem-vindas.