Recherche binaire en PHP

Qu'est-ce que la recherche binaire ?

La recherche binaire est un algorithme de recherche utilisé pour trouver efficacement la position d'une valeur cible dans un tableau (ou une liste) trié. Cela fonctionne en divisant à plusieurs reprises la plage de recherche en deux et en comparant l'élément du milieu à la valeur cible.

L'algorithme de recherche binaire suit les étapes suivantes :

• Commencez avec l'ensemble du tableau trié.

• Placez le pointeur gauche sur le premier élément du tableau et le pointeur droit sur le dernier élément.

• Calculez l'index du milieu comme la moyenne des pointeurs gauche et droit (division entière).

• Comparez la valeur à l'index du milieu à la valeur cible.

• Si la valeur intermédiaire est égale à la valeur cible, la recherche réussit et l'algorithme renvoie l'index.

• Si la valeur cible est supérieure à la valeur médiane, éliminez la moitié gauche de la plage de recherche en mettant à jour le pointeur gauche vers milieu + 1.

• Si la valeur cible est inférieure à la valeur médiane, éliminez la moitié droite de la plage de recherche en mettant à jour le pointeur droit au milieu - 1.

• Répétez les étapes 3 à 7 jusqu'à ce que la valeur cible soit trouvée ou que la plage de recherche soit vide (le pointeur gauche est plus grand que le pointeur droit).

• Si la plage de recherche est vide et que la valeur cible n'est pas trouvée, l'algorithme conclut que la valeur cible n'existe pas dans le tableau et renvoie -1 ou une indication appropriée.

La recherche binaire est un algorithme très efficace avec une complexité temporelle de O(log n), où n est le nombre d'éléments dans le tableau. Il est particulièrement efficace pour les grands tableaux triés car il réduit rapidement la portée de la recherche en la divisant en deux à chaque étape, permettant des recherches rapides même avec un grand nombre d'éléments.

Programme PHP de recherche binaire

Méthode 1 - Utiliser l'itération

Exemple

<?php
function binarySearch($arr, $target) {
   $left = 0;
   $right = count($arr) - 1;
   while ($left <= $right) {
      $mid = floor(($left + $right) / 2);
      // Check if the target value is found at the middle index
      if ($arr[$mid] === $target) {
         return $mid;
      }
      // If the target is greater, ignore the left half
      if ($arr[$mid] < $target) {
         $left = $mid + 1;
      }
      // If the target is smaller, ignore the right half
      else {
         $right = $mid - 1;
      }
   }
   // Target value not found in the array
   return -1;
}
// Example usage 1
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 91;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.<br>";
} else {
   echo "Target value found at index $resultIndex.<br>";
}
// Example usage 2
$targetValue = 42;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.";
} else {
   echo "Target value found at index $resultIndex.";
}
?>

Sortie

Target value found at index 9.
Target value not found in the array.

Méthode 2 - Utiliser la récursivité

Exemple

<?php
function binarySearchRecursive($arr, $target, $left, $right) {
   if ($left > $right) {
      // Target value not found in the array
      return -1;
   }
   $mid = floor(($left + $right) / 2);
   // Check if the target value is found at the middle index
   if ($arr[$mid] === $target) {
      return $mid;
   }
   // If the target is greater, search the right half
   if ($arr[$mid] < $target) {
      return binarySearchRecursive($arr, $target, $mid + 1, $right);
   }
   // If the target is smaller, search the left half
   return binarySearchRecursive($arr, $target, $left, $mid - 1);
}
// Wrapper function for the recursive binary search
function binarySearch($arr, $target) {
   $left = 0;
   $right = count($arr) - 1;
   return binarySearchRecursive($arr, $target, $left, $right);
}
// Example usage
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 16;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.";
} else {
   echo "Target value found at index $resultIndex.";
}
?>

Sortie

Target value found at index 4.

Conclusion

En résumé, la recherche binaire est un algorithme puissant qui peut trouver efficacement une valeur cible dans un tableau trié. Il fournit deux implémentations courantes : itérative et récursive. La méthode itérative utilise une boucle while pour diviser à plusieurs reprises la plage de recherche en deux jusqu'à ce que la valeur cible soit trouvée ou que la plage devienne vide. Sa mise en œuvre est simple et convient parfaitement à la plupart des scénarios. D'un autre côté, les méthodes récursives emploient des fonctions récursives pour effectuer des recherches binaires. Elle suit la même logique que la méthode itérative, mais utilise des appels de fonction au lieu de boucles. La recherche binaire récursive fournit une implémentation plus propre, mais peut entraîner une surcharge légèrement plus élevée en raison de la manipulation de la pile d'appels de fonction. Dans l’ensemble, les deux méthodes constituent un moyen efficace et fiable d’effectuer des opérations de recherche binaire.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!