Algoritmi de căutare

Căutarea stabilește dacă o valoare dată se află printre elementele unui vector și, în caz afirmativ, pe ce poziție. Programa prevede două metode: căutarea secvențială și căutarea binară.

Deosebirea dintre ele este de ordin de mărime. Într-un vector cu un milion de elemente, prima efectuează în cazul cel mai defavorabil un milion de comparații, a doua douăzeci. Căutarea binară cere însă o condiție: vectorul trebuie să fie ordonat.

Căutarea secvențială

Descrierea. Elementele vectorului se testează succesiv, de la primul spre ultimul, până la găsirea valorii căutate sau până la epuizarea vectorului.

Pașii algoritmului

i ← 1; gasit ← fals
cât timp i ≤ n și gasit = fals execută
    dacă v[i] = x atunci
        gasit ← adevărat; poz ← i
    altfel
        i ← i + 1
    sfdacă
sfcât timp

/* Întoarce poziția lui x în v[0..n-1], sau -1 dacă valoarea nu apare. */
int secventiala(int v[], int n, int x) {
    for (int i = 0; i < n; i++)
        if (v[i] == x) return i;
    return -1;
}

Observație. Metoda nu impune nicio condiție vectorului. Se aplică pe date neordonate, pe orice tip de elemente între care este definită egalitatea și pe structuri care se pot parcurge numai element cu element, cum sunt listele înlănțuite.

Ordinul de complexitate este O(n).

Căutarea binară

Descrierea. Vectorul fiind ordonat crescător, mulțimea indicilor [s, d] se împarte în două submulțimi prin indicele din mijloc, m. Se compară valoarea căutată cu elementul v[m]:

• dacă v[m] este egal cu valoarea căutată, poziția este m și căutarea se încheie;
• dacă v[m] este mai mic, valoarea căutată, dacă apare, se află printre elementele cu indici din [m+1, d];
• dacă v[m] este mai mare, valoarea căutată, dacă apare, se află printre elementele cu indici din [s, m−1].

La fiecare pas, mulțimea în care se mai caută se înjumătățește.

Pașii algoritmului

Se folosesc: s pentru primul indice al zonei în care se caută, d pentru ultimul, m pentru indicele elementului din mijloc și poz pentru poziția pe care s-a găsit valoarea. Cât timp valoarea nu a fost găsită, poz are valoarea 0.