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 majoritatea programatorilor ce termina facultatea de informatica nu reusesc sa scrie o cautare binara fara probleme.

*Buguri frecvente*

*Buguri frecvente:*

O implementare poate avea gramada de probleme cum ar fi:
* ciclu infinit

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. Ai un pas logic in plus la care trebuie sa fi atent. Cazurile la una din marginile sirului pot deveni mai dificile. Sau putem avea probleme de genul hi devine mai mic decat lo.

*Variante*

*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 de membrii infoarena utilizeaza puterile lui 2. Codul e elegant:

O solutie folosita frecvent de membrii infoarena foloseste puterile lui 2. Codul e elegant:

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

  for (i = 0; step; step >>= 1)
    if (i + step < N && A[i + step] <= x)
    i += step;

  if (A[i] == x)
    return i;
  else
    return -1;

  return i;

}
==