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 *multe buguri* in zone cum ar fi:

Implementarile pot avea buguri in multe 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>.

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

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

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

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