Voce se considera um bom programador?

bug

Você se considera um bom programador? Se respondeu sim a esta pergunta, então aposto que não vai deixar este bug passar despercebido:

E ai, vê alguma coisa?

 

Óbvio não?

 

 

Dica: olhe atentamente para a linha 6:

Ainda não percebeu? Então digamos, o que acontece, se, por acaso, low valer 10 e high valer 2.147.483.647 (ou seja, 2^31-1, o valor máximo que um inteiro de 32 bits pode possuir)?

Overflow!

Sim, de fato, a maioria das implementações de busca binária possui este erro. Não apenas livros, apostilas e materiais didáticos, mas sistemas críticos de produção também. Mas ai você fala: Ahh mas eu nunca vou empregar este tipo de busca em algo tão grande! – Bom, talvez não, mas não se esqueça que este é o mecanismo chave de muitos outros algoritmos de divisão-e-conquista, como, por exemplo, o mergesort.

 

Mais do que isto, esta observação serve para elucidar o quão é difícil garantir a corretude de um software. Demoraram 16 anos para detectar um erro no algoritmo que é, provavelmente, o mais popular de toda computação, presente em virtualmente todos os livros da área. Pois é: Planejamento cuidadoso é uma bênção, testar é uma maravilha. Utilizar métodos formais, melhor ainda. Revisão de código e análise estatística? Impossível ainda restar algum bug! Errado! Nenhuma destas coisas são suficientes para eliminarmos todos os bugs de um software. A verdade é: Eles sempre vão estar presentes e nos acompanhar por toda nossa vida :~

 

Ah, a correção? Simplesmente mude a linha 6 para:

Mágica.

 

[Fonte: Official Google Research Blog]

Leave a Reply

Your email address will not be published. Required fields are marked *