|

Algoritmi de Căutare – Căutarea Binara 19


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.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *