close

Algoritmo di ricerca binaria (Binary Search) in PHP: spiegazione, passaggi ed esempio

L'algoritmo di ricerca binaria è un metodo efficiente per trovare un valore specifico in un array ordinato. Questo approccio divide l'array in parti più piccole e confronta continuamente il valore nella posizione centrale dell'intervallo di ricerca con il valore target. Se i valori corrispondono, viene trovato il valore desiderato; in caso contrario, l'algoritmo continua a restringere l'intervallo di ricerca e ripete il processo finché non viene trovato il valore o non rimangono più elementi da esaminare.

Passi:

  1. Inizializza l'intervallo di ricerca: iniziare selezionando l'intervallo di ricerca dalla prima left  all'ultima posizione right  dell'array.
  2. Trova il punto medio: calcola il punto medio calcolando la media delle left posizioni e giuste; questo è il punto medio dell'intervallo di ricerca.
  3. Confronta valori: confronta il valore nel punto centrale con il valore target.
  4. Gestisci il risultato del confronto: se il valore nel punto centrale corrisponde al valore di destinazione, restituisci questa posizione. Se il valore nel punto centrale è inferiore al valore target, aggiorna la posizione sinistra al centro + 1 per cercare nella metà destra. Se il valore nel punto centrale è maggiore del valore di destinazione, aggiorna la posizione destra al centro- 1 per cercare nella metà sinistra.
  5. Ripeti: ripetere i passaggi da 2 a 4 finché non viene trovato il valore o non ci sono più elementi da controllare left > right.

Vantaggi e svantaggi

Vantaggi:

  • Prestazioni efficienti: la complessità temporale dell'algoritmo è O(log n), il che lo rende altamente efficiente per la gestione di set di dati di grandi dimensioni.
  • Efficace per set di dati di grandi dimensioni: la ricerca binaria è efficace nel ridurre il numero di elementi da esaminare rapidamente per set di dati di grandi dimensioni.

Svantaggi:

  • Applicabile solo agli array ordinati: l'algoritmo funziona solo su array ordinati.
  • Numero variabile di passaggi: il numero di passaggi necessari per trovare il valore dipende dalla sua posizione nell'array e può richiedere molti passaggi per i valori vicini alle estremità.

Esempio: ricerca binaria per trovare il valore 12 in un array ordinato in PHP 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

Spiegazione dell'esempio

  1. Iniziamo con l'intervallo di ricerca iniziale dalla prima left = 0 all'ultima posizione right = 6  dell'array.
  2. Calcoliamo il punto medio(mid) facendo la media delle posizioni sinistra e destra; mid = 3. Il valore a metà è 12.
  3. Confrontiamo il valore in mid(12) con il valore target(12) e troviamo una corrispondenza, quindi restituiamo la posizione 3.
  4. L'algoritmo termina e viene emesso il risultato "Valore 12 trovato nella posizione 3".