Pe scurt
Căutarea secvențială parcurge elementele unui vector unul câte unul până găsește valoarea căutată, având complexitatea O(n). Căutarea binară este mult mai eficientă (O(log n)), dar necesită ca vectorul să fie sortat și folosește principiul „divide et impera”, înjumătățind intervalul de căutare la fiecare pas.
Algoritmul de căutare secvențială (liniară)
Aceasta este cea mai simplă metodă de a găsi o valoare într-un vector. Algoritmul parcurge elementele unul câte unul, începând cu primul, până când găsește elementul căutat sau până când ajunge la sfârșitul vectorului.
- Complexitatea de timp este O(n) în cel mai rău caz, ceea ce înseamnă că pentru un vector cu n elemente, se efectuează până la n comparații
- Este utilă atunci când datele nu sunt sortate sau când vectorul este mic
- Algoritmul se poate opri mai devreme dacă elementul este găsit înainte de final
Exemplu: Avem vectorul v = [3, 7, 1, 9, 4] și căutăm valoarea 9.
- Pașii: i=0, v[0]!=9; i=1, v[1]!=9; i=2, v[2]!=9; i=3, v[3]==9 => găsit la poziția 3 (indexare de la 0)
- S-au efectuat 4 comparații
Algoritmul de căutare binară
Căutarea binară este mult mai eficientă, dar necesită ca vectorul să fie sortat crescător (sau descrescător).
- Principiul de funcționare este de tip „divide et impera”: se compară elementul căutat cu elementul din mijlocul intervalului curent
- Dacă este egal, căutarea se termină cu succes
- Dacă elementul căutat este mai mic decât cel din mijloc, atunci căutarea continuă în jumătatea stângă
- Dacă elementul căutat este mai mare decât cel din mijloc, atunci căutarea continuă în jumătatea dreaptă
- La fiecare pas, intervalul de căutare se înjumătățește, ceea ce duce la o complexitate de timp O(log n) în cel mai rău caz
- Implementarea se poate face iterativ (cu un ciclu while) sau recursiv
- Este important să se acorde atenție calculului corect al indicelui de mijloc, evitând depășirea limitei de memorie (de exemplu, mid = stânga + (dreapta - stânga) / 2)
Exemplu (element existent): v = [2, 5, 8, 12, 16, 23, 38, 45, 56], căutăm valoarea 23.
- Stânga=0, dreapta=8, mid=4, v[4]=16<23 => stânga=5
- mid=(5+8)/2=6, v[6]=38>23 => dreapta=5
- mid=(5+5)/2=5, v[5]=23 => găsit la poziția 5
- S-au efectuat doar 3 comparații
Exemplu (element inexistent): Același vector, căutăm valoarea 10.
- Stânga=0, dreapta=8, mid=4, v[4]=16>10 => dreapta=3
- mid=(0+3)/2=1, v[1]=5<10 => stânga=2
- mid=(2+3)/2=2, v[2]=8<10 => stânga=3
- mid=(3+3)/2=3, v[3]=12>10 => dreapta=2
- stânga (3) > dreapta (2) => nu există, returnează -1
- 4 comparații
Aplicații și adaptări
- Pentru Bacalaureat, trebuie să cunoașteți ambele metode, să le implementați corect în C/C++ și să analizați eficiența
- Un exemplu tipic: se dă un vector sortat de numere, se cere să se găsească poziția unui număr dat. Dacă numărul nu există, se returnează -1
- Căutarea binară poate fi adaptată pentru a găsi prima sau ultima apariție a unui element, ceea ce este util în probleme mai complexe
Verifică-te!
- Care este complexitatea de timp a căutării secvențiale în cel mai rău caz și în ce situații este recomandată utilizarea acesteia?
- De ce este necesar ca vectorul să fie sortat pentru a aplica căutarea binară?
- Câte comparații se efectuează pentru a găsi valoarea 38 în vectorul v = [2, 5, 8, 12, 16, 23, 38, 45, 56] folosind căutarea binară?