Căutarea secvențială

Căutarea secvențială verifică elementele pe rând până găsește valoarea sau ajunge la sfârșit. Nu cere un tablou sortat. În $[8;3;8]$, căutarea lui 3 găsește indicele 1; căutarea lui 5 nu găsește nicio poziție. Dacă sunt mai multe apariții, trebuie precizat dacă se cere prima, ultima sau toate.

Căutarea secvențială verifică elementele pe rând, de la primul spre ultimul, până când găsește valoarea căutată sau epuizează tabloul. Nu cere ca tabloul să fie sortat. Rezultatul este poziția elementului sau o convenție pentru „negăsit”, de obicei $-1$ (indicele 0 este valid, deci 0 nu poate fi folosit pentru negăsit). Dacă valoarea apare de mai multe ori, enunțul precizează dacă se cere prima, ultima sau fiecare apariție. În cel mai favorabil caz se face o singură comparație, iar în cel mai defavorabil $n$ comparații, deci timpul este $O(n)$, iar memoria auxiliară este constantă.

Exemplul 1 — prima apariție.

#include <iostream>
using namespace std;
int main() {
    int v[] = {8, 3, 8};
    int n = 3, cautat = 8, poz = -1;
    for (int i = 0; i < n && poz == -1; ++i)
        if (v[i] == cautat)
            poz = i;
    cout << poz;
    return 0;
}

La primul element, v[0] = 8, deci poz devine 0 și condiția poz == -1 face ciclul să se oprească. Se afișează 0. Pentru cautat = 5 se compară succesiv 8, 3 și 8 cu 5, nicio egalitate nu apare, poz rămâne $-1$ și ciclul se încheie când i ajunge la 3, după trei comparații. Abia după ce ai verificat toate elementele poți afirma că valoarea lipsește.

Exemplul 2 — toate aparițiile și ultima apariție. În tabloul $8,3,8,5,8$, valoarea 8 apare pe pozițiile 0, 2 și 4. Pentru a le afișa pe toate, ciclul nu se oprește la prima potrivire: afișează i de fiecare dată când v[i] == 8 și parcurge tot tabloul, cu 5 comparații. Pentru ultima apariție se poate folosi aceeași parcurgere, fără oprire, atribuind poz = i la fiecare potrivire; la sfârșit poz este 4. Alternativ, se parcurge tabloul de la sfârșit spre început și se oprește la prima potrivire.

Exemplul 3 — căutarea într-un tablou sortat se poate opri mai devreme. Dacă tabloul este sortat crescător, căutarea se oprește când elementul curent depășește valoarea căutată. Pentru $2,4,7,9$ și valoarea 5: se compară cu 2 (mai mic), cu 4 (mai mic), cu 7 (mai mare decât 5), deci 5 lipsește și căutarea s-a oprit după trei comparații, fără să mai verifice 9. Această oprire nu este posibilă într-un tablou nesortat. Pentru tablouri sortate mari, căutarea binară este mai rapidă.

Exemplul 4 — căutarea într-un șir de caractere. Aceeași metodă funcționează pe caractere. În șirul banana, litera a apare pe pozițiile 1, 3 și 5 (numerotare de la 0): prima apariție este la 1, ultima la 5, iar numărul aparițiilor este 3. Ciclul parcurge șirul până la caracterul terminator '\0', iar un contor și două variabile pentru prima și ultima poziție se actualizează la fiecare potrivire: prima poziție se fixează numai când este încă $-1$, iar ultima se rescrie de fiecare dată.

Invariantul ciclului. Înainte de a compara v[i], se știe că valoarea căutată nu apare printre v[0], ..., v[i-1]. Dacă ciclul se oprește prin poz != -1, poz este prima apariție; dacă se oprește prin i == n, valoarea lipsește.

Urmărește condiția de oprire: cu poz == -1 în condiția ciclului se păstrează prima poziție, iar fără ea aceeași buclă ar putea suprascrie poz cu ultima poziție găsită. La un tablou gol, rezultatul rămâne $-1$. Nu folosi „valoarea 0” drept marcaj universal pentru negăsire: indicele 0 este valid. Dacă ciclul are condiția i <= n pentru un tablou cu $n$ elemente, ultima iterație citește v[n], adică în afara tabloului, iar rezultatul poate depinde de o valoare nedefinită. Când se cere ultima apariție, nu pune condiția poz == -1 în ciclu. Când se cere numărul de comparații, distinge cazurile: valoarea de pe prima poziție cere una, valoarea de pe ultima sau o valoare absentă cer $n$. Pentru numărarea aparițiilor în $4,7,4,9,4$ cu $x=4$, contorul crește de trei ori, iar parcurgerea face toate cele 5 comparații, oriunde ar fi prima apariție.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int v[] = {4, 7, 4, 9, 4}, n = 5, x = 4, poz = -1;
for (int i = 0; i < n; i++)
    if (v[i] == x)
        poz = i;
cout << poz;

• a) -1
• b) 0
• c) 2
• d) 4

Răspunsul corect este d). Ciclul nu se oprește la prima potrivire: valoarea 4 se află pe pozițiile 0, 2 și 4, iar poz ia pe rând valorile 0, 2, 4. Ultima atribuire păstrează 4. Secvența determină ultima apariție a lui x. Varianta b) ar rezulta dacă ciclul s-ar opri la prima apariție, iar varianta a) ar apărea dacă valoarea ar lipsi.

Greșeli frecvente

• Greșit: valoarea 0 poate marca „negăsit”.
  Corect: 0 este un indice valid; se folosește o valoare precum -1.
• Greșit: într-un tablou nesortat, căutarea se poate opri la primul element mai mare decât valoarea căutată.
  Corect: această oprire e posibilă doar când tabloul este sortat.
• Greșit: dacă ciclul nu se oprește la prima potrivire, poz rămâne prima apariție.
  Corect: va fi suprascris și va păstra ultima apariție.

Înainte și după