Cautarea ta binara e gresita

Cosmin Negruseri
07 ianuarie 2012

Cautarea binara e probabil primul algoritm studiat de elevii sau studentii la informatica care exemplifica tehnica divide and conquer. Ideea de baza e simpla: folosindu-ne de monotonia datelor pe care cautam reducem 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.

Apar buguri frecvente cum ar fi intrare in ciclu infinit, algoritm gresit pentru siruri de scurte de lungime 0, 1, 2 sau siruri in care elementul cautat nu exista.

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.

Ideea de baza e ca vom folosi invarianti

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)
            low = mid;
        else
            hi = mid;
    }
    if (hi == A.length || A[hi] != x)
        return -1;
    else
        return hi;
}
=

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.

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 pe infoarena face cautare binara folosind puterile lui 2. Puteti vedea ca arata destul de misto:

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.

In 2006, Joshua Bloch, Google Java Architect care a scris algoritmul de cautare binara in java.util.Arrays a descoperit un bug in implementare. Puteti citi in detaliu aici. Pe scurt, lucrand la google el a ajuns sa sorteze siruri mai mari de un miliard de numere. Astfel pasul mid = (lo + hi) / 2 a ajuns sa depaseasca Integer.MAXINT care e 20000... Solutia pentru problema asta e sa folosim mid = lo + (hi - lo) / 2.