Căutarea într-un vector

Căutarea secvențială, căutarea binară pe vector sortat și de ce a doua schimbă ordinul de mărime al problemei.

Căutarea secvențială

Cauți o valoare uitându-te la fiecare element, pe rând.

int poz = 0;
for (int i = 1; i <= n; i++)
    if (v[i] == x) {
        poz = i;
        break;
    }

if (poz > 0) cout << "găsit pe poziția " << poz;
else cout << "nu există";

Convenția „poz = 0 înseamnă negăsit" funcționează pentru că lucrăm cu indici de la 1. Cu indexare de la 0, folosește -1.

Fără break ai găsi ultima apariție, nu prima. Uneori exact asta cere enunțul, deci citește-l cu atenție.

Varianta fără break, cu condiția în antet:

int i = 1;
while (i <= n && v[i] != x)
    i++;
if (i <= n) cout << "găsit pe poziția " << i;

Ordinea condițiilor din while este obligatorie. i <= n trebuie testat primul, altfel la ultima trecere v[i] se citește în afara vectorului. E exemplul clasic care arată de ce contează evaluarea leneșă a lui &&.

Costul: în cel mai rău caz n pași.

Căutarea binară

Dacă vectorul este sortat crescător, poți face mult mai bine.

Te uiți la elementul din mijloc. Dacă e egal cu ce cauți, gata. Dacă e mai mare, valoarea căutată nu poate fi decât în jumătatea stângă. Dacă e mai mic, poate fi doar în cea dreaptă. În ambele cazuri arunci jumătate din vector dintr-o singură comparație.

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;
}

Urmărit pe v = 2 4 7 9 13 20 28 și x = 13:

Trei pași în loc de cinci. Diferența crește foarte repede: 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 care trebuie nimerite

Condiția este st <= dr, nu st < dr. Cu <, când intervalul s-a redus la un singur element, acesta nu mai e verificat și căutarea ratează valori care există.

st = mij + 1 și dr = mij - 1, cu ±1. Fără el, când st și dr sunt vecine, intervalul nu se mai micșorează și bucla nu se mai termină.

Vectorul trebuie să fie sortat. Pe un vector nesortat, căutarea binară nu dă eroare, dar dă răspunsuri greșite. E condiția cel mai ușor de uitat.

Prima poziție pe care ar putea sta o valoare

Uneori nu vrei să știi dacă valoarea există, ci unde s-ar insera ca vectorul să rămână sortat, sau câte elemente sunt mai mici decât ea. Se rezolvă tot binar, dar fără oprire la egalitate:

int st = 1, dr = n + 1;
while (st < dr) {
    int mij = (st + dr) / 2;
    if (v[mij] < x) st = mij + 1;
    else dr = mij;
}
// st = prima poziție cu v[st] >= x

Așa afli și de câte ori apare x într-un vector sortat. Cauți prima poziție cu valoare ≥ x și prima cu valoare > x, iar diferența dintre ele este răspunsul.

Când merită sortat

Sortarea costă mai mult decât o căutare secvențială, deci pentru o singură căutare nu merită.

Merită când cauți de multe ori: sortezi o dată, apoi fiecare căutare e ieftină. Raționamentul apare des la problemele cu multe interogări.

De reținut

• Căutarea secvențială merge pe orice vector și costă n.
• În while (i <= n && v[i] != x), testul de margine trebuie să fie primul.
• Căutarea binară cere vector sortat și face atâția pași de câte ori poți înjumătăți n.
• st <= dr în condiție și mij ± 1 la actualizări. Altfel ratezi valori sau intri în buclă infinită.
• Pe vector nesortat, căutarea binară dă răspunsuri greșite fără nicio eroare.