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.

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.

*Buguri frecvente;*
O implementare poate avea gramada de probleme cum ar fi:
* ciclu infinit
* conditii gresite de terminare
* probleme siruri de scurte de lungime 0, 1, 2
* probleme pentru siruri in care x nu exista sau x apare de mai multe ori
* probleme cand x apare in apropiere de inceputul sau finalul sirului

*Cum sa implementezi o cautare binara corecta:*

Ideea de baza e ca vom folosi 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>)
Sa vedem cum arata codul: