Ricerca binaria in C++

La ricerca binaria è un algoritmo che viene usato per trovare gli elementi in un array ordinato; il fatto che sia ordinato è fondamentale e obbligatorio.

Questo algoritmo è più efficiente della ricerca sequenziale, in quanto usa la logica del divide et impera.

In sostanza si procede suddividendo l'array man mano che la ricerca non trova l'elemento, andando a ricercarlo solo in una parte dell'array, che diventa sempre più piccolo.

Quindi, partendo da un elemento casuale:

• se la chiave è uguale, abbiamo trovato l'elemento
• se la chiave è maggiore si prosegue cercando verso destra
• se la chiave è minore si prosegue cercando verso sinistra

Ecco perchè l'array deve essere ordinato.

Qui sotto un esempio in C++:

#include <bits/stdc++.h>

using namespace std;

int binarySearch(int arr[], int sx, int rx, int x) {
    if (rx >= sx) {
        int mid = sx + (rx - sx) / 2;

        if (arr[mid] == x) {
            return mid;
        }

        if (arr[mid] > x) {
            return binarySearch(arr, sx, mid - 1, x);
        }

        return binarySearch(arr, mid + 1, rx, x);
    }

    return -1;
}

int main(void) {
    int arr[] = { 20, 32, 51, 106, 400 };
    int x = 106;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? cout << "Elemento non trovato"
                             : cout << "Elemento trovato; Indice " << result;

    cout << "\n";
    return 0;
}

Enjoy!