Algoritmi de Căutare – Căutarea Secvențială 18
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ă?
- Se compară elementul căutat cu fiecare element din vector, pornind de la început.
- Dacă se găsește o potrivire, se returnează poziția elementului.
- 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:
- Cazul cel mai favorabil: O(1)
- Elementul căutat se află la prima poziție.
- Cazul cel mai defavorabil: O(n)
- Elementul căutat se află la ultima poziție sau nu există în vector.
- 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:
- Realizați un program care determină dacă o valoare introdusă de utilizator există într-un vector de numere reale.
- Modificați algoritmul pentru a afișa numărul total de apariții ale unei valori în vector.
- Implementați un program care verifică dacă un șir de caractere există într-un vector de șiruri.
6. Scheme logice:
- 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.