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.

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

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:

}
==

* conditia de la linia 3 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.
* la linia x stim ca A[mid] < x si astfel putem micsora spatiu de cautare si pastra invariantul, dandu-i lui lo valoarea mid
* la linia y stim ca A[mid] >= x si putem face atribuirea hi = mid.
* la linia z vedem daca x e in sir
** in caz afirmativ putem sa returnam indexul hi
** un caz negativ e ca A[A.length - 1] < x si atunci avem ca lo = A.length - 1 si hi = A.length
** alt 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.

Ideea e foarte flexibila. Acum puteti incerca sa schimbati invariantul pentru a rezolva probleme ca gasirea ultimei aparitii a lui x in sirul sortat, gasirea  predecesorului lui x in sir sau gasirea succesorului. Alt avantaj e ca folosind invarianti pentru cautarea binara, scriind algoritmul ii si demonstrati corectitudinea :).

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 abordare e detaliata in cartea Prgramming Pearls de Jon Bentley.