Ce este căutarea binară?

O căutare într-un vector sortat care se uită la elementul din mijloc și elimină jumătatea în care valoarea nu poate fi. Face cel mult vreo 20 de pași pentru un milion de elemente.

Căutarea binară găsește o valoare într-un vector sortat înjumătățind de fiecare dată zona de căutat. Te uiți la elementul din mijloc. Dacă e cel căutat, ai terminat. Dacă e mai mare, valoarea nu poate fi decât în jumătatea stângă, iar dacă e mai mic, doar în cea dreaptă.

int st = 1, dr = n, poz = 0;
while (st <= dr) {
    int mij = (st + dr) / 2;
    if (v[mij] == x) { poz = mij; break; }
    if (v[mij] < x) st = mij + 1;
    else dr = mij - 1;
}

Pentru un milion de elemente, căutarea secvențială face până la un milion de pași, iar cea binară cel mult douăzeci.

Detaliile pe care trebuie să le nimerești: condiția este st <= dr, nu st < dr. Actualizările sunt mij + 1 și mij - 1, altfel bucla nu se termină. Iar vectorul trebuie să fie sortat. Pe unul nesortat, căutarea binară nu dă eroare, dar dă răspunsuri greșite.

Este în programă la „căutare secvențială și binară”. Lecția despre căutare are și urmărirea pe un exemplu.

Lecția care merge mai departe: Căutarea într-un vector