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.

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.

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