Algoritmo di ricerca binaria (Binary Search) in C++: spiegazione, esempio e codice

L'algoritmo di ricerca binaria è un modo più efficiente di cercare un elemento specifico in un elenco ordinato. A differenza della ricerca lineare, che controlla gli elementi in sequenza, la ricerca binaria divide l'elenco a metà e confronta l'elemento di destinazione con l'elemento centrale. Questo processo viene ripetuto finché non viene trovato l'elemento di destinazione o l'intervallo di ricerca diventa vuoto.

Come funziona

1. Inizia con l'intero elenco ordinato.
2. Trova l'elemento centrale dell'intervallo di ricerca corrente.
3. Confronta l'elemento centrale con il valore di destinazione.
4. Se l'elemento centrale è uguale al valore target, la ricerca ha esito positivo.
5. Se l'elemento centrale è maggiore dell'obiettivo, cerca nella metà sinistra dell'intervallo.
6. Se l'elemento centrale è più piccolo del bersaglio, cerca nella metà destra dell'intervallo.
7. Ripetere i passaggi da 2 a 6 finché non viene trovato l'elemento di destinazione o l'intervallo di ricerca diventa vuoto.

Esempio

Consideriamo un elenco ordinato di numeri interi e desideriamo trovare il numero 34 utilizzando la ricerca binaria.

Elenco ordinato: {12, 23, 34, 45, 56, 67, 89, 90}

1. Inizia con l'intero elenco.
2. Elemento centrale: 56(posizione 4). Confronta con 34.
3. 56 è maggiore di 34. Cerca nella metà sinistra.
4. Nuovo elemento centrale: 23(posizione 1). Confronta con 34.
5. 23 è minore di 34. Cerca nella metà destra.
6. Nuovo elemento centrale: 45(posizione 3). Confronta con 34.
7. 45 è maggiore di 34. Cerca nella metà sinistra.
8. Nuovo elemento centrale: 34(posizione 2). Obiettivo trovato.

Esempio di codice in 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;  
}  

Nell'esempio fornito, la binarySearch funzione viene utilizzata per trovare il numero 34 in un elenco ordinato di numeri interi. Il risultato sarà la posizione 34 nell'elenco(le posizioni iniziano da 0) o -1 se il numero non viene trovato.