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

static public int search(int [] array, int target)
{
int high = array.length, low = -1, probe;
while (high - low > 1)
{
probe = (low + high) >>> 1;
if (array[probe] < target)
low = probe;
else
high = probe;
}
if (high == array.length || array[high] != target)
return -1;
else
return high;
}

....

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.