Comment implémenter l'algorithme de recherche binaire en PHP

小云云
Libérer: 2023-03-18 06:16:01
original
2100 Les gens l'ont consulté

Cet article présente principalement l'algorithme de demi-recherche implémenté en PHP, décrit brièvement le principe de la demi-recherche et analyse les compétences opérationnelles pertinentes de PHP en utilisant des méthodes récursives et non récursives pour implémenter l'algorithme de demi-recherche sous la forme d'exemples. Les amis dans le besoin peuvent se référer à ce qui suit, en espérant que cela puisse aider tout le monde.

Définition : Technologie de demi-recherche, qui est une recherche binaire. Son principe est que les enregistrements du tableau linéaire doivent être classés dans l'ordre des clés (généralement du plus grand au plus petit) et que le tableau linéaire doit être stocké de manière séquentielle.

L'idée de base de la demi-recherche : Prenez l'enregistrement du milieu comme objet de comparaison. Si la valeur donnée est égale au mot-clé de l'enregistrement du milieu, alors la recherche est réussie ; si Si la valeur donnée est inférieure à la clé de l'enregistrement du milieu, continuez la recherche ; si la valeur donnée est supérieure à la clé de l'enregistrement du milieu, continuez la recherche dans la moitié droite de l'enregistrement du milieu. Répétez le processus ci-dessus jusqu'à ce que la recherche réussisse ou qu'il n'y ait aucun enregistrement dans toutes les zones de recherche et que la recherche échoue.

Code d'implémentation :


<?php
//递归方式
function bin_recur_search($arr,$val){
  global $time;
  if(count($arr) >= 1){
    $mid = intval(count($arr) / 2);
    $time++;
    if($arr[$mid] == $val){
      return &#39;值为:&#39;.$arr[$mid].&#39;<br>查找次数:&#39;.$time.&#39;<br>&#39;;
    }elseif($arr[$mid] > $val){
      $arr = array_splice($arr,0,$mid);
      return bin_recur_search($arr, $val);
    }else{
      $arr = array_slice($arr,$mid + 1);
      return bin_recur_search($arr, $val);
    }
  }
  return &#39;未找到&#39;.$val;
}
//非递归方式
function bin_search($arr,$val){
  if(count($arr) >= 1){
    $low = 0;
    $high = count($arr);
    $time = 0;
    while($low <= $high){
      $time++;
      $mid = intval(($low + $high)/2);
      if($val == $arr[$mid]){
        return &#39;索引:&#39;.$mid.&#39;<br>值为:&#39;.$arr[$mid].&#39;<br>查找次数:&#39;.$time;
      }elseif($val > $arr[$mid]){
        $low = $mid + 1;
      }else{
        $high = $mid - 1;
      }
    }
  }
  return &#39;未找到&#39;.$val;
}
$arr = array(1,3,5,7,7,9,25,68,98,145,673,8542);
echo bin_recur_search($arr, 673);
echo bin_search($arr, 673);
?>
Copier après la connexion

Résultats d'exécution :

值为:673
查找次数:4
索引:10
值为:673
查找次数:4
Copier après la connexion

Recommandations associées :

Explication détaillée d'exemples de recherche binaire et de recherche binaire dans l'algorithme Java

Explication détaillée des compétences de recherche binaire javascript_javascript

javascript demi-recherche position du caractère dans le tableau (liste ordonnée)_compétences javascript

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
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
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal