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.

Cautarea binara este 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 pierdut puncte la o problema din cauza 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:

*O solutie isteata* folosita de membrii infoarena utilizeaza puterile lui 2.
== code(c) |

int binary_search(int A, int x) {

int binary_search(int[] A, int x) {

  int i, step, N = A.length;
  for (step = 1; step < N; step <<= 1);
  for (i = 0; step; step >>= 1)

*Cum implementezi simplu, corect, clar si flexibil o cautare binara*

Folosim un *invariant* in bucla cautarii binare, adica o asertiune care e adevarata de fiecare data cand intram in bucla. Pentru cazul nostru acest invariant e ca lo indica spre un element care e mai mic ca x sau spre -1 si hi indica spre un element mai mare sau egal cu x sau in A.length. Pe scurt <tex>A[lo] < x \le A[hi] </tex> (consideram <tex>A[-1] = -\infty</tex> si <tex>A[A.length] = +\infty</tex>)

Folosim un *invariant* in bucla cautarii binare, adica o asertiune care e adevarata de fiecare data cand intram in bucla. Pentru cazul nostru acest invariant e ca lo indica spre un element care e mai mic ca x sau spre -1 si hi indica spre un element mai mare sau egal cu x sau spre A.length. Pe scurt <tex>A[lo] < x \le A[hi] </tex> (consideram <tex>A[-1] = -\infty</tex> si <tex>A[A.length] = +\infty</tex>)

Sa vedem cum arata codul:
== code(c) |

int search(int[] A, int x) {

int binary_search(int[] A, int x) {

    int hi = A.length, lo = -1, mid;
    while (hi - lo > 1) {
      mid = (lo + hi) / 2;
      if (A[mid] < x)

        low = mid;

        lo = mid;

       else
         hi = mid;
    }

* linia 2: setam pe hi si lo inafara sirului, astfel invariantul e indeplinit si nu trebuie sa tratam cazuri speciale.
* linia 3: conditia de continuare a buclei e hi - lo > 1. Invariantul ales face ca hi si lo sa fie tot timpul distincte. La fiecare pas distanta intre hi si lo se injumatateste, iar cand hi si lo ajung consecutive ca pozitii in sir putem lua o decizie.
* linia 4: mid va fi tot timpul intre lo si hi.

* linia 6: stim ca A[mid] < x si astfel facand atribuirea lo = mid micsoram spatiu de cautare si pastra invariantul

* linia 6: stim ca A[mid] < x si astfel facand atribuirea lo = mid micsoram spatiu de cautare si pastram invariantul

* la linia 8 stim ca A[mid] >= x si putem face atribuirea hi = mid.
* la linia 10 vedem daca x e in sir
** in caz afirmativ putem sa returnam indexul hi

Am scapat de greselile ce le mentionam mai sus, pentru ca invariantul ne demonstreaza corectitudinea algoritmului nostru.
Ideea e foarte flexibila, putem schimba usor invariantul pentru a aborda variantele problemei mentionate. De exemplu pentru a gasi ultima pozitie din sir mai mica decat x putem folosi invariantul <tex>A[lo] \le x < A[hi]</tex>

Aceasta abordarea este detaliata in cartea Programming Pearls de Jon Bentley care v-o recomand.

Aceasta abordarea este detaliata in cartea Programming Pearls de Jon Bentley pe care v-o recomand.

*Linkbaitul din titlu :)*

Daca nu v-am convins de 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>.

Daca nu v-am convins de 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 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. La pasul mid = (lo + hi) / 2 s-a depasit Integer.MAX_VALUE care e 2147483647 si codul a declansat o exceptie. 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.