Algoritmi de cautare: cautare secventiala si binara (in vectori)

Căutarea în vectori este o operație fundamentală în informatică, prin care determinăm dacă o anumită valoare (numită „cheie”) se află într-un șir de elemente și, opțional, la ce poziție. Există două metode principale: căutarea secvențială (liniară) și căutarea binară.

Căutarea secvențială este cea mai simplă: parcurgem vectorul element cu element, de la primul la ultimul, și comparăm fiecare element cu cheia. Dacă găsim o potrivire, returnăm poziția respectivă; dacă ajungem la capăt fără succes, returnăm un indicator că elementul nu există (de obicei -1). Avantajul principal este că vectorul nu trebuie să fie sortat.

Dezavantajul este timpul de execuție: în cel mai rău caz (când cheia lipsește sau este ultima), parcurgem toate n elemente, deci complexitatea este O(n). Este metoda potrivită pentru liste mici sau nesortate.

Căutarea binară este mult mai eficientă, dar necesită ca vectorul să fie sortat crescător (sau descrescător). Ideea este să împărțim repetat intervalul de căutare în jumătate. Comparăm cheia cu elementul din mijlocul intervalului curent.

Dacă este egală, am găsit. Dacă cheia este mai mică, continuăm căutarea în jumătatea stângă; dacă este mai mare, în jumătatea dreaptă. Repetăm până când intervalul rămâne fără elemente (caz în care cheia nu există).

Complexitatea este O(log n), adică extrem de rapidă chiar și pentru vectori mari (de exemplu, pentru 1.000.000 de elemente, avem nevoie de cel mult 20 de comparații).

Comparație: Căutarea secvențială este simplă de implementat și nu impune condiții asupra datelor, dar este lentă pentru volume mari. Căutarea binară este rapidă, dar necesită sortare prealabilă (care poate fi costisitoare). În practică, dacă datele sunt sortate și căutăm frecvent, căutarea binară este alegerea optimă.

Exemplu concret: Avem vectorul [3, 7, 11, 15, 20]. Căutăm 11. Secvențial: verificăm 3, 7, 11 – găsit la poziția 2 (index 2). Binar: mijlocul este 11 (index 2) – găsit direct. Căutăm 5. Secvențial: parcurgem tot vectorul, nu găsim. Binar: mijlocul = 11 > 5, căutăm în stânga [3,7]; nou mijloc = 3 < 5, căutăm în dreapta [7]; mijloc = 7 > 5, nu mai avem elemente, deci nu există.

Exemple

• Exemplul 1: Căutare secvențială într-un vector nesortat. Vector: [8, 2, 5, 9, 1]. Căutăm cheia 5. Pași: comparăm 8 ≠ 5, 2 ≠ 5, 5 = 5 → găsit la poziția 2 (index 2). Dacă am fi căutat 10, am fi parcurs toate elementele și am fi returnat -1.
• Exemplul 2: Căutare binară într-un vector sortat. Vector: [2, 4, 6, 8, 10, 12, 14]. Căutăm cheia 10. Pas 1: stânga=0, dreapta=6, mijloc=3 (valoare 8). 10 > 8, deci căutăm în dreapta: stânga=4, dreapta=6, mijloc=5 (12). 10 < 12, căutăm în stânga: stânga=4, dreapta=4, mijloc=4 (10). 10 = 10 → găsit la index 4.
• Exemplul 3: Căutare binară când cheia lipsește. Același vector sortat [2,4,6,8,10,12,14], căutăm cheia 7. Pas 1: mijloc=3 (8), 7 < 8 → stânga=0, dreapta=2. Pas 2: mijloc=1 (4), 7 > 4 → stânga=2, dreapta=2. Pas 3: mijloc=2 (6), 7 > 6 → stânga=3, dreapta=2 → interval gol, return -1.

Concepte cheie: Căutare secvențială (liniară) – parcurgere element cu element, O(n), Căutare binară – împărțire repetată în jumătăți, O(log n), necesită vector sortat, Compararea eficienței: binară > secvențială pentru volume mari de date sortate