Algoritmi de Căutare – Căutarea Secvențială

---

1. Obiectivele lecției:

• Să înțeleagă principiul căutării secvențiale.
• Să implementeze algoritmul de căutare secvențială în limbajul C++.
• Să analizeze eficiența algoritmului (complexitatea în timp).
• Să aplice metoda pentru rezolvarea unor probleme practice.

---

2. Conținutul lecției:

Ce este căutarea secvențială?

• Definiție: Căutarea secvențială este o metodă simplă de căutare, în care se verifică fiecare element al unui vector în ordine, până când se găsește elementul căutat sau se ajunge la finalul vectorului.
• Aplicație: Este utilizată atunci când datele nu sunt sortate sau când se lucrează cu seturi de date mici.

---

Cum funcționează?

1. Se compară elementul căutat cu fiecare element din vector, pornind de la început.
2. Dacă se găsește o potrivire, se returnează poziția elementului.
3. Dacă nu se găsește elementul până la finalul vectorului, se indică faptul că nu există.

---

Pseudocod:

Intrare: vector, dimensiune, valoare_cautata

Pentru i de la 0 la dimensiune – 1:

    Dacă vector[i] == valoare_cautata:

        Returnează i

Returnează -1 (valoarea nu a fost găsită)

---

3. Cod în C++:

---

Exemplu de bază:

#include <iostream>

using namespace std;

int cautareSecventiala(int arr[], int n, int valoare_cautata) {

    for (int i = 0; i < n; i++) {

        if (arr[i] == valoare_cautata) {

            return i; // Returnează poziția unde a fost găsită valoarea

        }

    }

    return -1; // Valoarea nu a fost găsită

}

int main() {

    int arr[] = {4, 2, 7, 1, 9, 3};

    int n = sizeof(arr) / sizeof(arr[0]);

    int valoare_cautata;

    cout << „Introdu valoarea cautata: „;

    cin >> valoare_cautata;

    int rezultat = cautareSecventiala(arr, n, valoare_cautata);

    if (rezultat != -1) {

        cout << „Valoarea ” << valoare_cautata << ” a fost gasita la pozitia ” << rezultat << „.” << endl;

    } else {

        cout << „Valoarea ” << valoare_cautata << ” nu a fost gasita in vector.” << endl;

    }

    return 0;

}

---

Exemplu cu toate aparițiile unei valori:

#include <iostream>

using namespace std;

void cautareSecventialaToate(int arr[], int n, int valoare_cautata, int pozitii[], int& nr_pozitii) {

    nr_pozitii = 0; // Inițializăm numărul de poziții găsite la 0

    for (int i = 0; i < n; i++) {

        if (arr[i] == valoare_cautata) {

            pozitii[nr_pozitii] = i; // Stocăm poziția găsită

            nr_pozitii++;           // Incrementăm numărul de poziții găsite

        }

    }

}

int main() {

    int arr[] = {4, 2, 7, 2, 9, 3, 2};

    int n = sizeof(arr) / sizeof(arr[0]);

    int valoare_cautata;

    cout << „Introdu valoarea cautata: „;

    cin >> valoare_cautata;

    int pozitii[n]; // Tablou static pentru stocarea pozițiilor

    int nr_pozitii; // Variabilă pentru numărul de poziții găsite

    cautareSecventialaToate(arr, n, valoare_cautata, pozitii, nr_pozitii);

    if (nr_pozitii > 0) {

        cout << „Valoarea ” << valoare_cautata << ” a fost gasita la pozitiile: „;

        for (int i = 0; i < nr_pozitii; i++) {

            cout << pozitii[i] << ” „;

        }

        cout << endl;

    } else {

        cout << „Valoarea ” << valoare_cautata << ” nu a fost gasita in vector.” << endl;

    }

    return 0;

}

---

4. Complexitatea algoritmului:

1. Cazul cel mai favorabil: O(1)
   • Elementul căutat se află la prima poziție.
2. Cazul cel mai defavorabil: O(n)
   • Elementul căutat se află la ultima poziție sau nu există în vector.
3. Cazul mediu: O(n)
   • Elementul căutat este distribuit aleatoriu.

---

Avantaje:

• Simplu de implementat.
• Nu necesită vector sortat.

Dezavantaje:

• Ineficient pentru vectori mari.
• Timp de execuție proporțional cu dimensiunea vectorului.

---

5. Activități practice pentru elevi:

1. Realizați un program care determină dacă o valoare introdusă de utilizator există într-un vector de numere reale.
2. Modificați algoritmul pentru a afișa numărul total de apariții ale unei valori în vector.
3. Implementați un program care verifică dacă un șir de caractere există într-un vector de șiruri.

---

6. Scheme logice:

1. Căutare secvențială:
   • Start -> Inițializează index i=0 -> Compară arr[i] cu valoare_cautata -> (DA: Returnează i) / (NU: i++) -> Dacă i≥n: Returnează -1 -> Stop.

---

7. Concluzie:

• Căutarea secvențială este un algoritm de bază, ușor de implementat, dar cu o eficiență scăzută pentru vectori mari.
• Este utilă atunci când datele nu sunt sortate sau pentru probleme simple.
• Prin implementarea acestui algoritm, elevii vor învăța concepte fundamentale de iterare și comparare.

Algoritmi de Căutare – Căutarea Binara

---

1. Obiectivele lecției:

• Să înțeleagă principiul căutării binare.
• Să implementeze algoritmul de căutare binară în limbajul C++.
• Să analizeze eficiența algoritmului (complexitatea în timp).
• Să aplice metoda pentru rezolvarea unor probleme practice.

---

2. Conținutul lecției:

Ce este căutarea binară?

• Definiție: Căutarea binară este un algoritm eficient care presupune împărțirea repetată a unui vector sortat în două jumătăți și eliminarea jumătății în care elementul căutat nu poate exista.
• Condiție: Vectorul trebuie să fie sortat înainte de aplicarea căutării binare.

---

Cum funcționează?

1. Se determină mijlocul vectorului.
2. Se compară elementul mijlociu cu elementul căutat:
   • Dacă sunt egale, elementul este găsit.
   • Dacă elementul căutat este mai mic, căutarea continuă în jumătatea stângă.
   • Dacă elementul căutat este mai mare, căutarea continuă în jumătatea dreaptă.
3. Se repetă până când elementul este găsit sau până când intervalul devine gol.

---

Pseudocod:

Intrare: vector sortat, dimensiune, valoare_cautata

Inițializează left = 0, right = dimensiune – 1

Cât timp left <= right:

    Calculează mid = (left + right) / 2

    Dacă vector[mid] == valoare_cautata:

        Returnează mid

    Dacă vector[mid] < valoare_cautata:

        left = mid + 1

    Altfel:

        right = mid – 1

Returnează -1 (valoarea nu a fost găsită)

---

3. Cod în C++:

---

Exemplu: Căutare binară iterativă

#include <iostream>

using namespace std;

int cautareBinara(int arr[], int n, int valoare_cautata) {

    int left = 0, right = n – 1;

    while (left <= right) {

        int mid = left + (right – left) / 2;

        // Verifică dacă valoarea este la mijloc

        if (arr[mid] == valoare_cautata) {

            return mid;

        }

        // Dacă valoarea este mai mare, continuă căutarea în dreapta

        if (arr[mid] < valoare_cautata) {

            left = mid + 1;

        } else { // Continuă căutarea în stânga

            right = mid – 1;

        }

    }

    return -1; // Valoarea nu a fost găsită

}

int main() {

    int arr[] = {2, 3, 4, 10, 40};

    int n = sizeof(arr) / sizeof(arr[0]);

    int valoare_cautata;

    cout << „Introdu valoarea cautata: „;

    cin >> valoare_cautata;

    int rezultat = cautareBinara(arr, n, valoare_cautata);

    if (rezultat != -1) {

        cout << „Valoarea ” << valoare_cautata << ” a fost gasita la pozitia ” << rezultat << „.” << endl;

    } else {

        cout << „Valoarea ” << valoare_cautata << ” nu a fost gasita in vector.” << endl;

    }

    return 0;

}

---

Exemplu: Căutare binară recursivă

#include <iostream>

using namespace std;

int cautareBinaraRecursiva(int arr[], int left, int right, int valoare_cautata) {

    if (left > right) {

        return -1; // Valoarea nu a fost găsită

    }

    int mid = left + (right – left) / 2;

    // Verifică dacă valoarea este la mijloc

    if (arr[mid] == valoare_cautata) {

        return mid;

    }

    // Continuă căutarea în jumătatea stângă

    if (arr[mid] > valoare_cautata) {

        return cautareBinaraRecursiva(arr, left, mid – 1, valoare_cautata);

    }

    // Continuă căutarea în jumătatea dreaptă

    return cautareBinaraRecursiva(arr, mid + 1, right, valoare_cautata);

}

int main() {

    int arr[] = {2, 3, 4, 10, 40};

    int n = sizeof(arr) / sizeof(arr[0]);

    int valoare_cautata;

    cout << „Introdu valoarea cautata: „;

    cin >> valoare_cautata;

    int rezultat = cautareBinaraRecursiva(arr, 0, n – 1, valoare_cautata);

    if (rezultat != -1) {

        cout << „Valoarea ” << valoare_cautata << ” a fost gasita la pozitia ” << rezultat << „.” << endl;

    } else {

        cout << „Valoarea ” << valoare_cautata << ” nu a fost gasita in vector.” << endl;

    }

    return 0;

}

---

4. Complexitatea algoritmului:

1. Timp:
   • Cazul cel mai favorabil: O(1)
     • Elementul căutat este la mijloc.
   • Cazul cel mai defavorabil: O(logn)
     • Fiecare iterație reduce numărul de elemente analizate la jumătate.
2. Spațiu:
   • Iterativ: O(1)
   • Recursiv: O(logn) (datorită stivei recursiei).

---

Avantaje:

• Eficient pentru vectori mari.
• Complexitate scăzută în comparație cu căutarea secvențială.

Dezavantaje:

• Necesită un vector sortat.
• Mai complicat de implementat decât căutarea secvențială.

---

5. Activități practice pentru elevi:

1. Scrieți un program care implementează căutarea binară pentru un vector sortat descrescător.
2. Modificați algoritmul pentru a găsi prima apariție a unei valori în cazul unui vector cu elemente duplicate.
3. Implementați o funcție care sortează un vector și apoi efectuează căutarea binară asupra acestuia.

---

6. Scheme logice:

1. Căutare binară (iterativă):
   • Start -> Calculează mijlocul mid -> Compară arr[mid] cu valoare_cautata -> (DA: Returnează mid) / (NU: Actualizează left/right) -> Reia -> Stop.
2. Căutare binară (recursivă):
   • Start -> Calculează mijlocul mid -> Compară arr[mid] cu valoare_cautata -> (DA: Returnează mid) / (NU: Apelează recursiv cu left/right) -> Stop.

---

7. Concluzie:

• Căutarea binară este un algoritm extrem de eficient pentru vectori mari, dacă aceștia sunt sortați.
• Elevii pot înțelege mai bine divizarea problemei și optimizarea prin reducerea domeniului de căutare.
• Este un instrument fundamental în algoritmică și programare.