Căutare secvențială și binară (Bac)

Căutarea este o operație fundamentală în informatică, prin care se determină dacă un element (cheie) se află într-o mulțime de date și, eventual, poziția acestuia. În cadrul examenului de Bacalaureat la Informatică, sunt studiate două metode principale de căutare: căutarea secvențială (liniară) și căutarea binară (logaritmică).

Căutarea secvențială este cea mai simplă: se parcurge secvențial fiecare element al unei structuri de date (de obicei un vector unidimensional) și se compară cu cheia căutată. Algoritmul se oprește atunci când găsește elementul (returnând poziția) sau când ajunge la capătul structurii (returnând un indicator de negăsit, de exemplu -1). Complexitatea sa temporală este O(n) în cel mai rău caz (când elementul nu există sau este ultimul).

Este utilă pentru vectori nesortati sau pentru seturi mici de date.

Căutarea binară se aplică doar pe mulțimi sortate (crescător sau descrescător). Ideea de bază este de a împărți repetat intervalul de căutare în două părți egale, comparând cheia cu elementul din mijloc. Dacă cheia este mai mică, se continuă căutarea în jumătatea stângă; dacă este mai mare, în jumătatea dreaptă.

Procesul se repetă până când cheia este găsită sau intervalul rămâne gol. Complexitatea este O(log₂ n), ceea ce o face extrem de eficientă pentru volume mari de date. Este important ca vectorul să fie sortat în prealabil; altfel, rezultatul este incorect.

Exemple de utilizare în Bacalaureat:

• Probleme care cer găsirea unui element într-un vector de maxim 1000 de elemente (căutare secvențială este acceptabilă).
• Probleme care cer găsirea rapidă într-un vector sortat de mari dimensiuni (se recomandă căutarea binară).
• Implementarea căutării binare recursive sau iterative.
• Identificarea poziției de inserare pentru menținerea ordinii.

Aspecte pedagogice:

• Înțelegerea diferenței dintre structuri sortate și nesortate.
• Recunoașterea cazurilor când căutarea secvențială este singura opțiune (vector nesortat).
• Stăpânirea implementării iterative și recursive a căutării binare.
• Atenție la indexarea vectorilor (de obicei de la 0 sau 1 în pseudocod).
• Gestionarea cazurilor limită (vector gol, cheie mai mică decât primul element, etc.).

La Bacalaureat, se cere adesea scrierea unui program complet în C/C++ sau Pascal, iar evaluarea pune accent pe corectitudinea logicii, tratarea tuturor cazurilor și eficiența algoritmului.

Exemple

• Exemplul 1: Căutare secvențială într-un vector nesortat. Se dă vectorul V = [3, 7, 1, 9, 4] și cheia=9. Se parcurg elementele: V[0]=3≠9, V[1]=7≠9, V[2]=1≠9, V[3]=9=9 => se returnează poziția 3 (indice 3, de la 0). Dacă cheia ar fi 2, s-ar ajunge la final și s-ar returna -1.
• Exemplul 2: Căutare binară într-un vector sortat crescător. V = [1, 4, 7, 9, 12, 15], cheia=7. Se inițializează stânga=0, dreapta=5. Mijloc = (0+5)/2 = 2 (valoarea 7). Comparăm: V[2]=7 == cheie => return poziția 2. Dacă cheia era 10, atunci: mijloc=2 (7<10) => stânga=3; nou mijloc=(3+5)/2=4 (valoarea 12>10) => dreapta=3; mijloc=(3+3)/2=3 (9<10) => stânga=4; stânga>dreapta => return -1.
• Exemplul 3: Căutare binară recursivă. Funcția cauta(V, st, dr, cheie) apelează mijloc; dacă V[mij]==cheie returnează mij; dacă st>dr returnează -1; dacă cheie < V[mij] apelează cauta(V,st,mij-1,cheie); altfel cauta(V,mij+1,dr,cheie). Exemplu: V=[2,5,8,10,13], cheie=5. Apel inițial: st=0, dr=4, mij=2 (8>5) => apel st=0, dr=1, mij=0 (2<5) => apel st=1, dr=1, mij=1 (5==5) => return 1.

Concepte cheie: Căutare secvențială: parcurgere liniară, complexitate O(n), se aplică pe orice vector (sortat sau nu)., Căutare binară: divizare repetată a intervalului, complexitate O(log n), necesită vector sortat., Implementare iterativă și recursivă a căutării binare., Condiții de oprire la căutarea binară (stânga > dreapta)., Atenție la indexarea de la 0 sau 1 și la tipul datelor.