InformaticăliceuClasa 9usor
Căutare Binară în C++ - Implementare și Aplicații
Algoritm eficient de căutare în vectori sortați cu complexitate O(log n). Include variante iterative și recursive.
circa 2 luni în urmă
0 vizualizări
20 minute
Căutare Binară în C++
Ce este Căutarea Binară?
Căutarea binară este un algoritm eficient pentru găsirea unui element într-un vector sortat, reducând spațiul de căutare la jumătate la fiecare pas.
Varianta Iterativă
1#include <iostream> 2#include <vector> 3using namespace std; 4 5int cautareBinara(const vector<int>& v, int x) { 6 int st = 0, dr = v.size() - 1; 7 8 while (st <= dr) { 9 int mid = st + (dr - st) / 2; 10 11 if (v[mid] == x) 12 return mid; 13 else if (v[mid] < x) 14 st = mid + 1; 15 else 16 dr = mid - 1; 17 } 18 19 return -1; // Nu a fost găsit 20} 21 22int main() { 23 vector<int> v = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}; 24 int x = 23; 25 26 int rezultat = cautareBinara(v, x); 27 28 if (rezultat != -1) 29 cout << "Element gasit la pozitia " << rezultat << endl; 30 else 31 cout << "Element negasit" << endl; 32 33 return 0; 34}
Varianta Recursivă
1int cautareBinaraRec(const vector<int>& v, int x, int st, int dr) { 2 if (st > dr) 3 return -1; 4 5 int mid = st + (dr - st) / 2; 6 7 if (v[mid] == x) 8 return mid; 9 else if (v[mid] < x) 10 return cautareBinaraRec(v, x, mid + 1, dr); 11 else 12 return cautareBinaraRec(v, x, st, mid - 1); 13}
Lower Bound și Upper Bound
1// Primul element >= x 2int lowerBound(const vector<int>& v, int x) { 3 int st = 0, dr = v.size(); 4 while (st < dr) { 5 int mid = st + (dr - st) / 2; 6 if (v[mid] < x) 7 st = mid + 1; 8 else 9 dr = mid; 10 } 11 return st; 12} 13 14// Primul element > x 15int upperBound(const vector<int>& v, int x) { 16 int st = 0, dr = v.size(); 17 while (st < dr) { 18 int mid = st + (dr - st) / 2; 19 if (v[mid] <= x) 20 st = mid + 1; 21 else 22 dr = mid; 23 } 24 return st; 25}
Complexitate
- •Timp: O(log n)
- •Spațiu: O(1) iterativ, O(log n) recursiv
Tutorialul te-a ajutat?
Dacă ai nevoie de ajutor personalizat, găsește un profesor calificat pentru meditații
