Você se considera um bom programador? Se respondeu sim a esta pergunta, então aposto que não vai deixar este bug passar despercebido:
|
1 |
1: <strong>public</strong> <strong>static</strong> <strong>int</strong> binarySearch(int[] a, int key) {<br />2: <strong>int</strong> low = 0;<br />3: <strong>int</strong> high = a.length - 1;<br />4:<br />5: <strong>while</strong> (low <= high) {<br />6: <strong>int</strong> mid = (low + high) / 2;<br />7: <strong>int</strong> midVal = a[mid];<br />8:<br />9: <strong>if</strong> (midVal < key)<br />10: low = mid + 1<br />11: <strong>else if</strong> (midVal > key)<br />12: high = mid - 1;<br />13: <strong>else</strong><br />14: return mid; // key found<br />15: }<br />16: <strong>return</strong> -(low + 1); // key not found.<br />17: }<br /> |
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:
[Fonte: Official Google Research Blog]