Bug secreto na busca binária

“Busca binária é um algoritmo notoriamente difícil de programar corretamente. Somente dezessete anos depois da invenção do algoritmo a primeira versão correta do programa foi publicada!”

Fonte.

Começo com essa citação pois fiquei assustado ao tomar conhecimento dela. Dezessete anos, para a computação isso é muito tempo para algo ficar “funcionando errado”. Não imagino que as funções tivessem erros óbvios. Provavelmente funcionavam com uma quantidade N de números em Y condições, mas em algum momento (talvez raro) quebrassem.

Eu utilizo a seguinte versão, que resolve todos os meus problemas atuais:

int buscaBin(int lista[], int numBusca, int tam)
{
  int esquerda,direita,meio;

  esquerda=0;
  direita=tam-1;

  while(esquerda <= direita)
  {
    meio=(esquerda+direita)/2;

    if(lista[meio] == numBusca)
      return meio;

    if(lista[meio] > numBusca)
      direita = meio-1;

    else esquerda = meio+1;
  }

  return -1;

}

Posso garantir que não vai quebrar em nenhuma condição? Não. Especialmente depois que li isso aqui, no blog de pesquisa da Google:

I remember vividly Jon Bentley’s first Algorithms lecture at CMU, where he asked all of us incoming Ph.D. students to write a binary search, and then dissected one of our implementations in front of the class. Of course it was broken, as were most of our implementations.

“Me lembro bem da primeira aula de Algoritmos de Jon Bentley na CMU [Carnegie Mellon University], onde ele nos pediu, todos novos estudantes Ph.D, para escrever uma busca binária. Em seguida ele dissecou uma de nossas implementações na frente da sala. É claro que ela estava quebrada, como estavam a maioria de nossas implementações.”

Fast forward to 2006. I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug.

“Avançando para 2006. Eu fiquei chocado [CHOQUEI!] quando descobri que a busca binária que Bentley provou estar correta e posteriormente testou no capítulo 5 de Programming Pearls contem um bug”

Fonte. Original em ingles, traduções feitas por mim.

Itálicos vermelhos são notas que acrescentei ao texto.

O bug é um problema temporal. Digo temporal pois envolve um “estouro” do limite do tipo inteiro. Nos anos 80 nem se pensava nisso, mas parece que a Google e outras empresas tiveram a honra estourá-lo.

Na minha implementação, o bug está nessa linha:

meio=(esquerda+direita)/2;

Imagine que esquerda+direita ultrapasse o limite. O valor vai ficar maluco, provavelmente negativo e tchau-tchau resultado condizente.

No artigo da Google, Joshua Bloch dá algumas sugestões de correção, mas ao meu ver, o próximo erro não tarda a surgir. A “manha”, pelo que entendi, é simplesmente aumentar a capacidade das variáveis. Ele mesmo se previne quanto a correção:

And now we know the binary search is bug-free, right? Well, we strongly suspect so, but we don’t know.

“E agora nós sabemos que a busca binária está livre de bugs, certo? Bem, nos suspeitamos que sim, mas não sabemos.”

Já estamos em 2009 e nada de novos bugs. Será que temos mais um, escondido, esperando nossa distração para atacar?

Cya!

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s