Cautarea binara printre primii algorimi divide and conquer studiati la informatica. Algoritmul rezolva problema gasirii unui element x in un sir sortat A folosind monotonia elementelor pentru a injumatati la fiecare pas spatiul de cautare. Ideea algoritmului e simpla, insa aproape fiecare concurent olimpiada de informatica are cate o poveste cum a bushit o problema din implementarii. Majoritatea studentilor de informatica si chiar doctoranzilor, dupa cum ne spune Jon Bentley in Programming Pearls, nu reusesc sa scrie o cautare binara fara probleme.

Implementarile pot avea buguri in multe zone cum ar fi:

Implementarile pot avea *multe buguri* in zone cum ar fi:

* intrare ciclu infinit
* conditii gresite de terminare

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>.

In urmatorul articol voi discuta ce probleme pot aparea la cautarea binara pe numere reale sau metoda bisectiei cum mai e numita.

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 :).