Am vazut 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.

 
*Variante:*
Problema poate aparea in versiuni diferite cu ar fi gasirea primei sau ultimei aparitii a lui x in sirul sortat, gasirea  predecesorului sau succesorului valorii x in sir. Astfel ar fi utila o metoda care poate fi adaptata usor la astfel de cerinte.
 
 

O solutie folosita frecvent de membrii infoarena foloseste puterile lui 2. Codul e elegant:
== code(c) |

int binary_search(int A, int val) {

int binary_search(int A, int x) {

  int i, step, N = A.length;
  for (step = 1; step < N; step <<= 1);
  for (i = 0; step; step >>= 1)

    if (i + step < N && A[i + step] <= val)

    if (i + step < N && A[i + step] <= x)

    i += step;
  return i;
}
==

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

Mie nu imi place aceasta varianta. Un dezavantaj e ca un programator are nu stie trucul intelege codul de mai sus mai greu. Nu am incercat sa vad cat de flexibila e solutia pentru cazuri in care x nu e in sir sau nu vrem prima aparitie a lui x in sir.

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

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

Folosind un invariant am demonstrat corectitudinea cautarii.
*Variante:*

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

Ideea e foarte flexibila. Alt avantaj e ca folosind invarianti pentru cautarea binara, scriind algoritmul ii si demonstrati corectitudinea :).

Aceasta abordare e detaliata in cartea Programming Pearls de Jon Bentley.