Ricerca binaria in PHP

Mattepuffo's logo
Ricerca binaria in PHP

Ricerca binaria in PHP

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.

Detto ciò, vediamo un esempio in PHP:

$arr = array(20, 32, 51, 106, 400);
$n = count($arr);
$x = 106;
$result = binarySearch($arr, 0, $n - 1, $x);

if (($result == -1)) {
    echo "Elemento non trovato";
} else {
    echo "Elemento trovato; Indice " . $result;
}

function binarySearch($arr, $lx, $rx, $x) {
    if ($rx >= $lx) {
        $mid = ceil($lx + ($rx - $lx) / 2);

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

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

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

    return -1;
}

Enjoy!


Share this Post

Commentami!