Căutarea secvențială

A căuta într-un vector înseamnă a stabili dacă o anumită valoare există printre elemente și, eventual, pe ce poziție se află. Cea mai simplă și mai generală metodă de căutare este cea secvențială.

Marele avantaj al căutării secvențiale este că funcționează pe orice vector, indiferent dacă elementele sunt ordonate sau nu. Practic, este metoda la care apelăm ori de câte ori nu avem un motiv întemeiat să folosim altceva.

Parcurgem vectorul cu o structură repetitivă și comparăm fiecare element cu valoarea căutată x. Dacă găsim o potrivire, afișăm poziția:

int n, v[1001], x;
// ...
for (int i = 0; i < n; i++)
    if (v[i] == x)
        cout << i << ' ';

Acest cod afișează toate pozițiile pe care apare valoarea x. Condiția din interiorul buclei poate fi adaptată la cerința problemei: în loc de egalitate am putea căuta, de exemplu, primul număr par, ultimul element negativ sau orice altă proprietate.

De multe ori ne interesează doar dacă valoarea există și care este prima ei poziție. În acest caz putem opri căutarea imediat ce am găsit-o, folosind o variabilă care reține poziția (sau -1 dacă valoarea nu apare):

int poz = -1;
for (int i = 0; i < n && poz == -1; i++)
    if (v[i] == x)
        poz = i;
if (poz != -1)
    cout << "Gasit pe pozitia " << poz;
else
    cout << "Nu exista";

Oprirea căutării la prima potrivire ne scutește de parcurgerea inutilă a restului vectorului.

În cazul cel mai defavorabil (valoarea nu există sau se află la final), căutarea secvențială parcurge toate cele n elemente, deci are o complexitate de ordinul $O(n)$. Pentru vectori mari și ordonați există o metodă mult mai rapidă: căutarea binară.

Căutarea secvențială este metoda universală de regăsire a unei valori într-un vector: simplă, sigură și aplicabilă oricărui șir. Atunci când vectorul este ordonat, însă, putem profita de această proprietate pentru a căuta mult mai eficient, prin căutarea binară.