Maison  >  Article  >  développement back-end  >  Analyse d'algorithme PHP : Comment utiliser un algorithme de recherche binaire pour localiser rapidement des éléments dans un tableau ordonné ?

Analyse d'algorithme PHP : Comment utiliser un algorithme de recherche binaire pour localiser rapidement des éléments dans un tableau ordonné ?

王林
王林original
2023-09-19 13:14:01883parcourir

Analyse dalgorithme PHP : Comment utiliser un algorithme de recherche binaire pour localiser rapidement des éléments dans un tableau ordonné ?

Analyse d'algorithme PHP : Comment utiliser un algorithme de recherche binaire pour localiser rapidement des éléments dans un tableau ordonné ?

Vue d'ensemble :
L'algorithme de recherche binaire est un algorithme de recherche efficace, adapté à la recherche d'éléments spécifiques dans des tableaux ordonnés. Cet article présentera en détail le principe de l'algorithme de recherche binaire et donnera des exemples de code PHP.

  1. Principe :
    L'algorithme de recherche binaire localise rapidement l'élément cible en réduisant de moitié la plage de recherche à plusieurs reprises. Le processus est le suivant :
  2. Tout d'abord, réduisez la plage de recherche au début et à la fin du tableau
  3. Ensuite, calculez l'index de l'élément du milieu et comparez-le avec l'élément cible
  4. Si l'élément cible est égal ; à l'élément du milieu, renvoie directement le succès de la recherche ;
  5. Si l'élément cible est plus petit que l'élément du milieu, cela signifie que l'élément cible est sur le côté gauche de l'élément du milieu et la plage de recherche sera rétrécie vers la gauche moitié ;
  6. Si l'élément cible est plus grand que l'élément du milieu, cela signifie que l'élément cible est sur le côté droit de l'élément du milieu, et la recherche sera La plage est réduite à la moitié droite
  7. Répétez ce qui précède ; étapes jusqu'à ce que l'élément cible soit trouvé ou que la plage de recherche soit vide, indiquant que la recherche a échoué.
  8. Exemple de code :
    Ce qui suit est un exemple de code de recherche binaire implémenté 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;                    // 找到目标元素,返回索引
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1;               // 目标元素在中间元素的右侧
        } else {
            $right = $mid - 1;              // 目标元素在中间元素的左侧
        }
    }

    return -1;                              // 查找失败,返回-1
}

// 示例用法
$sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
$targetElement = 11;
$result = binarySearch($sortedArray, $targetElement);

if ($result == -1) {
    echo "目标元素 $targetElement 不存在于数组中。";
} else {
    echo "目标元素 $targetElement 的索引是 $result。";
}

Dans l'exemple ci-dessus, nous avons défini deux variables nommées binarySearch的函数来实现二分查找。函数接受两个参数:有序数组$arr和目标元素$target。函数运行的过程中,使用了$left$right pour représenter les limites gauche et droite de la plage de recherche, en ajustant constamment la Limites. Affinez la portée de la recherche et trouvez enfin l'élément cible ou déterminez qu'il n'existe pas.

Enfin, nous avons défini un exemple d'utilisation qui montre comment utiliser l'algorithme de recherche binaire pour trouver un élément spécifique dans un tableau ordonné et afficher le résultat.

Conclusion : 
L'algorithme de recherche binaire est un algorithme de recherche efficace, adapté à la recherche d'éléments spécifiques dans des tableaux ordonnés. En réduisant continuellement la portée de la recherche, la recherche binaire peut localiser rapidement l'élément cible. Dans le développement réel, nous pouvons combiner des algorithmes de recherche binaires pour la conception de code en fonction des besoins afin d'améliorer l'efficacité de la recherche.

【Nombre de mots : 451 mots】

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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn