Cautarea ta binara este gresita

Cautarea ta binara e gresita

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.

Cautarea binara e probabil primul algoritm studiat de elevii sau studentii la informatica care exemplifica tehnica divide and conquer. Ea rezolva problema gasirii unui element x in un sir sortat A. Ideea de baza e simpla: folosindu-ne de monotonia datelor putem reduce la fiecare pas problema la jumatate. Totusi aproape fiecare concurent olimpiada de informatica are cate o poveste cum a bushit o problema din cauza unei cautari binare. La fel in interviurile de programare marea majoritatea a canditatilor nu reusesc sa scrie o cautare binara care sa mearga corect pe toate cazurile.

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

Apar buguri frecvente cum ar fi intrare in ciclu infinit, algoritm gresit pentru siruri de scurte de lungime 0, 1, 2, pentru siruri in care x nu exista sau x apare de mai multe ori.

* intrare ciclu infinit
* conditii gresite de terminare
* siruri scurte de lungime 0, 1, 2
* siruri in care x nu exista sau x apare de mai multe ori
* siruri in care x apare in apropiere de inceput sau final

Jon Bentley trateaza problema cautarii binare in detaliu in Programming Pearls. Va fac un scurt rezumat despre cum putem scrie o cautare binara fara greseli.

*Optimizari premature*
Am vazut tot felul de variante, de exemplu unii testeaza daca a[mid] e egal cu x si scurt circuiteaza cautarea. Aceasta optimizare nu ajuta in cazul general, doar complica codul. Alta varianta e sa reduci mai mult problema folosind hi = mid - 1 sau lo = mid + 1. Optimizarea e mica si adauga un pas logic in plus la care trebuie sa fii atent. Cazurile la una din marginile sirului pot deveni mai dificile sau putem avea probleme de genul hi devine mai mic decat lo.
 
Multe implementari sunt "blindate" ca să evite bug-urile de mai sus. Problema e că lumea le blindează cu cod duplicat si error prone, repetand conditii.
 
*Variante ale problemei*
Exista versiuni diferite cum ar fi gasirea primei sau ultimei aparitii a lui x in sirul sortat, gasirea  predecesorului sau succesorului valorii x in sir.
 
 
*O solutie isteata* folosita de membrii infoarena utilizeaza puterile lui 2.
 
== code(c) |
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)
    if (i + step < N && A[i + step] <= x)
    i += step;
  if (A[i] == x)
    return i;
  else
    return -1;
}
==
 
Aceasta varianta de implementare este eleganta insa mie nu imi place foarte tare. Dezavantajul principal este lizibilitatea codului.
 
*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 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>)

Ideea de baza e ca vom folosi un invariant in bucla cautarii binare. Pentru cazul nostru acesti 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>)

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

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

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

    int hi = A.length, lo = -1, mid;
    while (hi - lo > 1) {

      mid = (lo + hi) / 2;
      if (A[mid] < x)
        lo = mid;
       else
         hi = mid;

        mid = (lo + hi) / 2;
        if (A[mid] < x)
            low = mid;
        else
            hi = mid;

    }
    if (hi == A.length || A[hi] != x)
        return -1;

}
==

* 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 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
** un caz negativ e cand ultimul element din sir e mai mic decat x. Atunci avem lo = A.length - 1 si hi = A.length
** celalalt caz negativ e ca hi sa fie undeva in interiorul sirului si sa avem ca A[lo] < x < A[hi]

Invariantul este <tex>A[lo] < x \le A[hi] </tex> (pentru simplitate consideram <tex>A[-1] = -\infty</tex> si <tex>A[A.length] = +\infty</tex>). La fiecare pas injumatatim distanta intre lo si hi. Observam ca invariantul face ca lo sa fie tot timpul diferit de hi si astfel conditia continuare e hi - lo > 1 nu hi - lo > 0. Cand hi si lo sunt consecutive putem lua o decizie, sa returnam A[hi] daca x e in sir sau -1 daca x nu apare in sir.

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>

O data ce ati inteles ideea de mai sus, veti vedea cum puteti schimba invariantul usor pentru a rezolva probleme ca gasirea ultimei aparitii a lui x in sirul sortat, gasirea  predecesorului lui x in sir sau gasirea succesorului.

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

Mai vezi tot felul de variante, de exemplu sa testezi daca a[mid] e egal cu x si sa iesi din cautare mai repede. Asta nu ajuta in cazul general deci putem sari peste. Alta varianta e ca poti reduce ceva mai mult problema folosind hi = mid - 1 sau lo = mid + 1. Asta face putin mai greu de verificat invariantul cautarii si s-ar putea sa apara probleme la cazuri in care cautarea ajunge la una dintre marginile sirului.
 
Alta solutie care e folosita frecvent de membrii infoarena face cautare binara folosind puterile lui 2. Puteti vedea ca arata destul de misto:
 
== code(c) |
int binary_search(int A, int val) {
  int i, step, N = A.length;
  for (step = 1; step < N; step <<= 1);
  for (i = 0; step; step >>= 1)
    if (i + step < N && A[i + step] <= val)
    i += step;
  return i;
}
==

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

Mie nu imi place aceasta varianta. Un dezavantaj ar fi ca un programator nou care nu stie trucul o sa inteleaga mai greu codul, si nu stiu daca e la fel de usor de modificat ca sa gasesti succesorul lui x sau ultima aparitie a lui x si asa mai departe.

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

Daca v-am suparat cu linkbaitul 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 bug care aparea in majoritatea cautarilor binare sau a sortarilor prin interclasare scrise in ultimii 20 de ani. Pe scurt, 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 mid = lo + (hi - lo) / 2 in loc de mid = (hi + lo) / 2.

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

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

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

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

protected

private

6864