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ă?
- Se determină mijlocul vectorului.
- 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ă.
- 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:
- 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.
- Cazul cel mai favorabil: O(1)
- 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:
- Scrieți un program care implementează căutarea binară pentru un vector sortat descrescător.
- Modificați algoritmul pentru a găsi prima apariție a unei valori în cazul unui vector cu elemente duplicate.
- Implementați o funcție care sortează un vector și apoi efectuează căutarea binară asupra acestuia.
6. Scheme logice:
- Căutare binară (iterativă):
- Start -> Calculează mijlocul mid -> Compară arr[mid] cu valoare_cautata -> (DA: Returnează mid) / (NU: Actualizează left/right) -> Reia -> Stop.
- 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.