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.

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 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:

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.

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.

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.

Aceasta abordare e detaliata in cartea Prgramming Pearls de Jon Bentley.
 
Apar 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 ca poti reduce ceva mai mult problema folosind hi = mid - 1 sau lo = mid + 1. Pentru mie e putin mai greu de verificat invariantul cautarii, avand un pas logic in plus. Pe langa asta cazurile in care ajungem la una din marginile sirului pot deveni mai dificile.

Alta solutie care e folosita frecvent de membrii infoarena face cautare binara folosind puterile lui 2. Puteti vedea ca arata destul de misto:

O solutie folosita frecvent de membrii infoarena foloseste puterile lui 2. Puteti vedea ca arata destul de misto:

== code(c) |
int binary_search(int A, int val) {

}
==

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.

Mie nu imi place aceasta varianta. Un dezavantaj e ca un programator are nu stie trucul intelege codul de mai sus mai greu.

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.

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 <tex>mid = lo + (hi - lo) / 2</tex> in loc de <tex>mid = (hi + lo) / 2</tex>.

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