close

Algorithme de recherche binaire (Binary Search) en PHP : explication, étapes et exemple

L'algorithme de recherche binaire est une méthode efficace pour trouver une valeur spécifique dans un tableau trié. Cette approche divise le tableau en parties plus petites et compare en permanence la valeur à la position médiane de la plage de recherche avec la valeur cible. Si les valeurs correspondent, la valeur souhaitée est trouvée ; sinon, l'algorithme continue à réduire la plage de recherche et répète le processus jusqu'à ce que la valeur soit trouvée ou qu'il ne reste plus d'éléments à examiner.

Pas:

  1. Initialiser la plage de recherche: Commencez par sélectionner la plage de recherche de la première position left  à la dernière position right  du tableau.
  2. Trouvez le point médian: Calculez le point médian en faisant la moyenne des left positions et de droite ; c'est le milieu de la plage de recherche.
  3. Comparer les valeurs: Comparez la valeur au milieu avec la valeur cible.
  4. Gérer le résultat de la comparaison : si la valeur au milieu correspond à la valeur cible, renvoie cette position. Si la valeur au milieu est inférieure à la valeur cible, mettez à jour la position gauche au milieu + 1 pour rechercher la moitié droite. Si la valeur au milieu est supérieure à la valeur cible, mettez à jour la position droite au milieu- 1 pour rechercher la moitié gauche.
  5. Répéter: Répétez les étapes 2 à 4 jusqu'à ce que la valeur soit trouvée ou qu'il n'y ait plus d'éléments à vérifier left > right.

Avantages et inconvénients

Avantages:

  • Performances efficaces : la complexité temporelle de l'algorithme est O(log n), ce qui le rend très efficace pour gérer de grands ensembles de données.
  • Efficace pour les grands ensembles de données : la recherche binaire est efficace pour réduire le nombre d'éléments à examiner rapidement pour les grands ensembles de données.

Désavantages:

  • Applicable uniquement aux tableaux triés : l'algorithme ne fonctionne que sur les tableaux triés.
  • Nombre variable d'étapes : le nombre d'étapes nécessaires pour trouver la valeur dépend de sa position dans le tableau, et il peut prendre plusieurs étapes pour les valeurs proches des extrémités.

Exemple: Recherche binaire pour trouver la valeur 12 dans un tableau trié en 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.";  
}

Explication de l'exemple

  1. Nous commençons par la plage de recherche initiale de la première position left = 0 à la dernière position right = 6  du tableau.
  2. Nous calculons le point médian(mid) en faisant la moyenne des positions gauche et droite; mid = 3. La valeur au milieu est 12.
  3. Nous comparons la valeur à mid(12) avec la valeur cible(12) et trouvons une correspondance, nous renvoyons donc la position 3.
  4. L'algorithme se termine et nous produisons le résultat "Valeur 12 trouvée en position 3".