Exemple d'explication de l'algorithme de recherche binaire implémenté en PHP

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 associées 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 qui en ont besoin peuvent Pour référence,

L'exemple de cet article décrit l'algorithme de demi-recherche implémenté en PHP. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

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);
?>

Résultat d'exécution :

值为:673
查找次数：4
索引：10
值为：673
查找次数：4

Articles qui pourraient vous intéresser :

Exemple d'algorithme de correspondance de chaînes implémenté en PHP

Un exemple de l'algorithme de correspondance maximale implémenté en PHP

Installation et utilisation de l'outil d'analyse des performances PHP xhprof et précautions associées

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!