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.

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.

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.

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.

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 invarianti
 
static public int search(int [] array, int target)
{
    int high = array.length, low = -1, probe;
    while (high - low > 1)
    {
        probe = (low + high) >>> 1;
        if (array[probe] < target)
            low = probe;
        else
            high = probe;
    }
    if (high == array.length || array[high] != target)
        return -1;
    else
        return high;
}
 
....

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.