Metode de Căutare: Secvențială și Binară

Bun, hai să vorbim despre cele două metode fundamentale de căutare: CĂUTAREA SECVENȚIALĂ și CĂUTAREA BINARĂ. Nu sunt doar algoritmi – sunt două moduri complet diferite de a gândi și de a rezolva problema “găsește acul în carul cu fân”.

1. Problema de Bază: “Găsește Cheia în Grămadă”

Ipoteză: Ai o colecție de elemente și vrei să găsești un anumit element.

Exemplu concret:

Vector: [5, 2, 8, 1, 9, 3, 7]
Vrem să găsim: 9

2. Căutarea Secvențială (Liniară): “Verifică Toate, Una Câte Una”

Strategie: Începi de la început și verifici fiecare element până îl găsești sau ajungi la sfârșit.

#include <iostream>
using namespace std;

int main() {
    int v[] = {5, 2, 8, 1, 9, 3, 7};
    int n = 7;
    int cautat = 9;

    bool gasit = false;
    int pozitie = -1;

    for(int i = 0; i < n; i++) {
        if(v[i] == cautat) {
            gasit = true;
            pozitie = i;
            break;  // Opresc imediat ce l-am găsit
        }
    }

    if(gasit) {
        cout << "Am gasit " << cautat << " pe pozitia " << pozitie << endl;
    } else {
        cout << "Nu am gasit " << cautat << " in vector!" << endl;
    }

    return 0;
}

Cum funcționează pas cu pas:

Caut 9 în [5, 2, 8, 1, 9, 3, 7]

Pas 1: v[0] = 5 → nu e 9
Pas 2: v[1] = 2 → nu e 9  
Pas 3: v[2] = 8 → nu e 9
Pas 4: v[3] = 1 → nu e 9
Pas 5: v[4] = 9 → DA! GĂSIT!

Caracteristici căutare secvențială:

• Funcționează pe orice vector (nesortat sau sortat)
• Simplu de implementat
• În cel mai rău caz: verifică toate elementele
• Complexitate: O(n)

3. Căutarea Binară: “Împarte și Câștigă”

ATENȚIE: Funcționează DOAR pe vectori SORTAȚI!

Strategie: Împarte vectorul în jumătate, decide în care jumătate se află elementul, repetă.

#include <iostream>
using namespace std;

int main() {
    // VECTOR SORTAT!
    int v[] = {1, 2, 3, 5, 7, 8, 9};
    int n = 7;
    int cautat = 5;

    int stanga = 0;
    int dreapta = n - 1;
    bool gasit = false;
    int pozitie = -1;

    while(stanga <= dreapta) {
        int mijloc = (stanga + dreapta) / 2;

        cout << "Caut intre pozitiile " << stanga << " si " << dreapta 
             << " (mijloc=" << mijloc << ", valoare=" << v[mijloc] << ")" << endl;

        if(v[mijloc] == cautat) {
            gasit = true;
            pozitie = mijloc;
            break;
        }

        if(v[mijloc] < cautat) {
            stanga = mijloc + 1;  // Caut în dreapta
            cout << "  → Merg la dreapta" << endl;
        } else {
            dreapta = mijloc - 1;  // Caut în stânga
            cout << "  → Merg la stanga" << endl;
        }
    }

    if(gasit) {
        cout << "\nAm gasit " << cautat << " pe pozitia " << pozitie << endl;
    } else {
        cout << "\nNu am gasit " << cautat << " in vector!" << endl;
    }

    return 0;
}

Cum funcționează pas cu pas:

Caut 5 în [1, 2, 3, 5, 7, 8, 9] (SORTAT!)

Pas 1: stanga=0, dreapta=6, mijloc=3, v[3]=5 → GĂSIT! (doar 1 pas!)

Un exemplu mai lung:

Caut 7 în [1, 2, 3, 5, 7, 8, 9]

Pas 1: stanga=0, dreapta=6, mijloc=3, v[3]=5
       5 < 7 → merg la dreapta

Pas 2: stanga=4, dreapta=6, mijloc=5, v[5]=8  
       8 > 7 → merg la stânga

Pas 3: stanga=4, dreapta=4, mijloc=4, v[4]=7 → GĂSIT!

4. Compararea Cele Două Metode

#include <iostream>
using namespace std;

int main() {
    cout << "=== COMPARATIE CĂUTARE SECVENȚIALĂ vs BINARĂ ===\n\n";

    cout << "CĂUTAREA SECVENȚIALĂ:\n";
    cout << "• Funcționează pe orice vector (nesortat sau sortat)\n";
    cout << "• Simplu de implementat\n";
    cout << "• În cel mai rău caz: verifică TOATE elementele\n";
    cout << "• Complexitate: O(n)\n";
    cout << "• Pentru 1.000.000 elemente: maxim 1.000.000 verificări\n\n";

    cout << "CĂUTAREA BINARĂ:\n";
    cout << "• Funcționează DOAR pe vectori SORTAȚI\n";
    cout << "• Mai complex de implementat\n";
    cout << "• În cel mai rău caz: verifică log₂(n) elemente\n";
    cout << "• Complexitate: O(log n)\n";
    cout << "• Pentru 1.000.000 elemente: maxim 20 verificări!\n";

    return 0;
}

5. Tabel Comparativ

Caracteristică	Căutare Secvențială	Căutare Binară
Vector necesar	Orice vector	DOAR vectori SORTAȚI
Implementare	Simplă	Mai complexă
Complexitate	O(n)	O(log n)
Timp 1.000.000 elem	~500.000 verificări (în medie)	~20 verificări
Când să folosești	Vectori nesortați sau mici	Vectori sortați mari

6. Variante ale Algoritmilor

6.1 Căutare secvențială cu poziția tuturor aparițiilor

#include <iostream>
using namespace std;

int main() {
    int v[] = {5, 2, 5, 1, 5, 3, 5};
    int n = 7;
    int cautat = 5;

    cout << "Caut toate aparitiile lui " << cautat << ":\n";

    for(int i = 0; i < n; i++) {
        if(v[i] == cautat) {
            cout << "Gasit pe pozitia " << i << endl;
        }
    }

    return 0;
}

6.2 Căutare binară recursivă

#include <iostream>
using namespace std;

int cautareBinaraRec(int v[], int stanga, int dreapta, int cautat) {
    if(stanga > dreapta) {
        return -1;  // Nu am găsit
    }

    int mijloc = (stanga + dreapta) / 2;

    if(v[mijloc] == cautat) {
        return mijloc;  // Am găsit!
    }

    if(v[mijloc] < cautat) {
        return cautareBinaraRec(v, mijloc + 1, dreapta, cautat);
    } else {
        return cautareBinaraRec(v, stanga, mijloc - 1, cautat);
    }
}

int main() {
    int v[] = {1, 2, 3, 5, 7, 8, 9};
    int n = 7;

    int poz = cautareBinaraRec(v, 0, n-1, 5);
    cout << "Gasit pe pozitia: " << poz << endl;

    return 0;
}

7. Când Să Folosești Care?

Folosește căutarea SECVENȚIALĂ când:

1. Vectorul e nesortat
2. Vectorul e mic (sub 100 elemente)
3. Cauți toate aparițiile unui element
4. Vectorul se modifică des (nu merită să-l sorți)

Folosește căutarea BINARĂ când:

1. Vectorul e sortat (sau poate fi sortat)
2. Vectorul e mare (peste 1000 elemente)
3. Faci multe căutări pe același vector
4. Viteza e importantă

8. Demonstrație de Performanță

#include <iostream>
#include <ctime>
using namespace std;

int main() {
    const int N = 1000000;  // 1 milion de elemente!
    int* v = new int[N];

    // Generez un vector sortat
    for(int i = 0; i < N; i++) {
        v[i] = i * 2;  // Numere pare: 0, 2, 4, 6, ...
    }

    int cautat = 500000;  // Caut un element din mijloc

    // Test căutare secvențială
    cout << "Caut " << cautat << " in " << N << " elemente:\n\n";

    clock_t start = clock();

    // Căutare secvențială
    bool gasitSecvential = false;
    for(int i = 0; i < N; i++) {
        if(v[i] == cautat) {
            gasitSecvential = true;
            break;
        }
    }

    clock_t end = clock();
    double timpSecvential = double(end - start) / CLOCKS_PER_SEC;

    cout << "Cautare secventiala: " << timpSecvential << " secunde\n";

    // Test căutare binară
    start = clock();

    // Căutare binară
    bool gasitBinar = false;
    int stanga = 0, dreapta = N - 1;

    while(stanga <= dreapta) {
        int mijloc = (stanga + dreapta) / 2;

        if(v[mijloc] == cautat) {
            gasitBinar = true;
            break;
        }

        if(v[mijloc] < cautat) {
            stanga = mijloc + 1;
        } else {
            dreapta = mijloc - 1;
        }
    }

    end = clock();
    double timpBinar = double(end - start) / CLOCKS_PER_SEC;

    cout << "Cautare binara:      " << timpBinar << " secunde\n";

    if(timpSecvential > 0) {
        cout << "\nBINARA e de " << timpSecvential/timpBinar << "x mai rapida!\n";
    }

    delete[] v;
    return 0;
}

9. Probleme Practice

Problema 1: Căutare în vector nesortat (doar secvențială)

#include <iostream>
using namespace std;

int main() {
    int v[] = {5, 2, 8, 1, 9, 3, 7};  // NESORTAT
    int n = 7;
    int cautat;

    cout << "Ce numar cauti? ";
    cin >> cautat;

    bool gasit = false;

    for(int i = 0; i < n; i++) {
        if(v[i] == cautat) {
            cout << "Gasit pe pozitia " << i << endl;
            gasit = true;
            break;
        }
    }

    if(!gasit) {
        cout << "Nu am gasit numarul!" << endl;
    }

    return 0;
}

Problema 2: Verifică dacă un vector e sortat (pentru căutare binară)

#include <iostream>
using namespace std;

bool esteSortat(int v[], int n) {
    for(int i = 0; i < n-1; i++) {
        if(v[i] > v[i+1]) {
            return false;  // NU e sortat
        }
    }
    return true;  // E sortat
}

int main() {
    int v[] = {1, 2, 3, 5, 7, 8, 9};
    int n = 7;

    if(esteSortat(v, n)) {
        cout << "Vectorul este sortat - pot folosi cautare binara!\n";
    } else {
        cout << "Vectorul NU este sortat - folosesc cautare secventiala!\n";
    }

    return 0;
}

Problema 3: Căutare binară cu verificare la limită

#include <iostream>
using namespace std;

int main() {
    int v[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int n = 10;

    int cautat;
    cout << "Ce numar cauti? ";
    cin >> cautat;

    // Verific dacă numărul se află în intervalul vectorului
    if(cautat < v[0] || cautat > v[n-1]) {
        cout << "Numarul nu se afla in vector!" << endl;
        return 0;
    }

    // Căutare binară normală...

    return 0;
}

10. Exerciții de Înțelegere

Exercițiul 1: Completează căutarea secvențială

int v[] = {5, 2, 8, 1, 9};
int n = 5;
int cautat = 8;
bool gasit = false;

for(int i = 0; i < n; i++) {
    if(/* condiție */) {
        gasit = true;
        cout << "Gasit pe pozitia " << /* ce pui aici? */;
        break;
    }
}

Soluție:

if(v[i] == cautat) {
    // ...
    cout << "Gasit pe pozitia " << i;
}

Exercițiul 2: Ce face acest cod?

int stanga = 0, dreapta = n-1;
while(stanga <= dreapta) {
    int mijloc = (stanga + dreapta) / 2;
    if(v[mijloc] == x) return mijloc;
    if(v[mijloc] < x) stanga = mijloc + 1;
    else dreapta = mijloc - 1;
}
return -1;

Răspuns: Este algoritmul de căutare binară.

Exercițiul 3: Când căutarea binară NU funcționează?

int v[] = {5, 2, 8, 1, 9};  // NESORTAT
// Căutare binară aici ar da rezultate greșite!

Schema de Decizie: Ce Algoritm Să Folosești

Ai un vector și vrei să cauți un element:

┌─────────────────────────────────────┐
│ Vectorul e sortat?                   │
│         ├─── DA ───► Folosește BINARĂ│
│         NO                           │
│         ▼                            │
│ Vectorul e mic (<100)?               │
│         ├─── DA ───► Folosește SECVENȚIALĂ│
│         NO                           │
│         ▼                            │
│ Vrei să-l sorți pentru multe căutări?│
│         ├─── DA ───► Sortează + BINARĂ│
│         NO                           │
│         ▼                            │
│ Folosește SECVENȚIALĂ                │
└─────────────────────────────────────┘

În concluzie:

• Căutarea secvențială = simplă, merge mereu, dar lentă pentru vectori mari
• Căutarea binară = rapidă, dar merge doar pe vectori sortați

Regula de aur:

• Vector nesortat sau mic → secvențială
• Vector sortat și mare → binară
• Dacă faci multe căutări pe un vector, merită să-l sorți o dată și apoi să folosești căutarea binară