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ă

Copiază
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ă

Copiază
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

Copiază
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