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.

Cautarea binara e probabil primul algoritm studiat de elevii sau studentii la informatica care exemplifica tehnica divide and conquer. Ideea de baza e simpla: folosindu-ne de monotonia datelor pe care cautam reducem 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 sau siruri in care elementul cautat nu exista.
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
 
Sa vedem cum arata codul:

Ideea de baza e ca vom folosi invarianti

== code(c) |
int search(int[] A, int x) {
    int hi = A.length, lo = -1, mid;

    // invariantul: A[lo] < x <= A[hi]
    // consideram A[-1] == -oo si A[A.length] == +oo

    while (hi - lo > 1) {
        mid = (lo + hi) / 2;
        if (A[mid] < x)

}
==

Invariantul este A[lo] < x <= A[hi] (pentru simplitate consideram A[-1] == -oo si A[A.length] == +oo). 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.
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.