Ricerca binaria

Cercare in un array in tempo O(n) è una buona soluzione, ma può essere ulteriormente ottimizzata a O(log n) usando un metodo chiamato ricerca binaria. 

Condizione per usare la ricerca binaria: Gli elementi dell'array devono essere ordinati in ordine crescente o decrescente.

Per esempio, 

int Arr[]={1,2,3,4,5};
int Brr[]={5,3,9,6,7};

In Arr, possiamo applicare la ricerca binaria per trovare un elemento, poiché tutti gli elementi di Arr sono ordinati in ordine crescente.

Non possiamo applicare la ricerca binaria a Brr, poiché gli elementi di Brr sono disposti casualmente.

Logica di base

Controlla l'elemento esattamente al centro dell'array, 

1. Se è uguale alla chiave, stampalo,
2.  se è minore dell'elemento chiave, cerca nella parte destra dell'array rimanente, 
3.  se è maggiore, cerca nella parte sinistra dell'array rimanente.

Ripeti il processo finché non trovi l'elemento chiave che cerchi; altrimenti, restituisci -1.

Procedura dettagliata

1. Per prima cosa inizializziamo 2 variabili che indicano l'inizio e la fine dell'array. Poi usiamo un ciclo while con una condizione: l'inizio deve essere sempre minore della fine.

    int s=0; //inizio
    int e=n; //fine
    
    while(s<=e){
    
    }

2. Trova l'elemento centrale calcolando (s+e)/2. Se mid è esattamente uguale alla chiave, restituiscilo.

    int s=0; //inizio
    int e=n; //fine
    
    while(s<=e){
    
        int mid=(s+e)/2;  //Metà dell'array

        if(arr[mid]==key){   //se è uguale, restituiscilo
            return mid;
        }
    
    }

3. Se l'elemento centrale è maggiore dell'elemento chiave, significa che la chiave deve trovarsi nella parte sinistra dell'array. Quindi spostiamo la fine dell'array a mid-1. Ora abbiamo un array di dimensione n/2, su cui ripetiamo questo processo.

    int s=0; //inizio
    int e=n; //fine
    
    while(s<=e){
    
        int mid=(s+e)/2;  //Metà dell'array

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;         //Sposta la fine a mid-1
        }
    
    }

4. Se nessuna di queste condizioni è vera, è chiaro che l'elemento deve essere maggiore dell'elemento centrale; quindi cerchiamo nella parte destra dell'array e, per farlo, spostiamo l'inizio dell'array alla posizione mid+1.

    int s=0;
    int e=n;
    while(s<=e){
        int mid=(s+e)/2;

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;
        }
        else{
            s=mid+1;   //Sposta l'inizio a mid+1
        }
    }

Eseguiamo il programma finché non troviamo l'elemento; se l'elemento non è presente, restituiamo -1.

Complessità temporale

A ogni passaggio, il numero di elementi si dimezza. Questo significa che il tempo di esecuzione di ogni passaggio è la metà di quello del passaggio precedente. In altre parole, il tempo si riduce in modo logaritmico, portando la complessità temporale della ricerca binaria a O(log n).