Algoritm de căutare binar (Binary Search) în C++- Explicație, Exemplu și Cod

Algoritmul de căutare binar este o modalitate mai eficientă de căutare a unui anumit element într-o listă sortată. Spre deosebire de căutarea liniară, care verifică elementele secvenţial, căutarea binară împarte lista în jumătăţi şi compară elementul ţintă cu elementul din mijloc. Acest proces se repetă până când elementul țintă este găsit sau intervalul de căutare devine gol.

Cum functioneaza

1. Începeți cu întreaga listă sortată.
2. Găsiți elementul din mijloc al intervalului de căutare curent.
3. Comparați elementul din mijloc cu valoarea țintă.
4. Dacă elementul din mijloc este egal cu valoarea țintă, căutarea are succes.
5. Dacă elementul din mijloc este mai mare decât ținta, căutați în jumătatea stângă a intervalului.
6. Dacă elementul din mijloc este mai mic decât ținta, căutați în jumătatea dreaptă a intervalului.
7. Repetați pașii 2-6 până când elementul țintă este găsit sau intervalul de căutare devine gol.

Exemplu

Să luăm în considerare o listă sortată de numere întregi și să găsim numărul 34 folosind căutarea binară.

Listă sortată: {12, 23, 34, 45, 56, 67, 89, 90}

1. Începeți cu întreaga listă.
2. Element mijlociu: 56(pozitia 4). Comparați cu 34.
3. 56 este mai mare decât 34. Căutați în jumătatea stângă.
4. Element de mijloc nou: 23(poziția 1). Comparați cu 34.
5. 23 este mai mic decât 34. Căutați în jumătatea dreaptă.
6. Element de mijloc nou: 45(poziția 3). Comparați cu 34.
7. 45 este mai mare decât 34. Căutați în jumătatea stângă.
8. Element de mijloc nou: 34(poziția 2). Țintă găsită.

Exemplu de cod în C++

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

În exemplul dat, binarySearch funcția este folosită pentru a găsi numărul 34 într-o listă sortată de numere întregi. Rezultatul va fi poziția 34 în listă(pozițiile încep de la 0) sau -1 dacă numărul nu este găsit.