Daca v-a sarit in ochi afirmatia din titlu, va mai zic ca in 2006, Joshua Bloch, cel care a scris algoritmul de cautare binara in java.util.Arrays a 'descoperit un bug':http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html in implementare. Acest bug care aparea in majoritatea cautarilor binare sau a sortarilor prin interclasare scrise in ultimii 20 de ani. Lucrand la Google el a ajuns sa sorteze siruri de doua miliarde de numere. Astfel pasul mid = (lo + hi) / 2 a ajuns sa depaseasca Integer.MAX_VALUE care e 2147483647. Putem rezolva bugul folosind <tex>mid = lo + (hi - lo) / 2</tex> in loc de <tex>mid = (hi + lo) / 2</tex>.

_Despre cautare binara pe numere reale sau metoda bisectiei in episodul urmator :)._
 

Stiu ca “You can’t teach an old dog new tricks” dar sper ca v-am convins de utilitatea invariantilor.

Voi ati avut vreodata probleme cu cautarile binare? Ce varianta folositi?

 
Voi ati avut vreodata probleme cu cautarile binare? Ce varianta folositi?
 
Despre cautare binara pe numere reale sau metoda bisectiei in episodul urmator :).