Algoritmi de căutare

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ă

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ă

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.

s ← 1; d ← n; poz ← 0
cât timp s ≤ d și poz = 0 execută
    m ← [(s + d) / 2]
    dacă v[m] = x atunci
        poz ← m
    altfel
        dacă v[m] < x atunci
            s ← m + 1
        altfel
            d ← m - 1
        sfdacă
    sfdacă
sfcât timp

int binara(int v[], int n, int x) {
    int st = 0, dr = n - 1;

    while (st <= dr) {
        /* Mijlocul se calculează astfel, nu ca (st + dr) / 2: pentru
           vectori foarte mari, suma celor doi indici poate depăși
           domeniul tipului int. */
        int mij = st + (dr - st) / 2;

        if (v[mij] == x) return mij;
        if (v[mij] < x) st = mij + 1;
        else            dr = mij - 1;
    }

    return -1;
}

Varianta recursivă, cerută la subcapitolul despre subprograme recursive:

int binaraRec(int v[], int st, int dr, int x) {
    if (st > dr) return -1;

    int mij = st + (dr - st) / 2;

    if (v[mij] == x) return mij;
    if (v[mij] < x) return binaraRec(v, mij + 1, dr, x);
    return binaraRec(v, st, mij - 1, x);
}

Exemplu. Vectorul 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, cu indici de la 0 la 9. Se caută valoarea 23.