Partage d'algorithme de recherche binaire de liste ordonnée PHP (demi-recherche)

Cet article présente principalement l'algorithme de recherche binaire (recherche par moitié) de recherche de table ordonnée en PHP. Il présente brièvement le concept et le principe de la méthode de recherche binaire et analyse la recherche de table linéaire ordonnée en PHP basée sur l'algorithme de recherche binaire en PHP. sous forme d'exemples. Les amis qui en ont besoin peuvent se référer aux compétences opérationnelles pertinentes. J'espère que cela pourra aider tout le monde.

Introduction :

Technologie de recherche binaire, également connue sous le nom de demi-recherche. 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 petit au plus grand) et que le tableau linéaire doit être stocké de manière séquentielle.

Idée de base :

Dans une liste ordonnée, prenez l'enregistrement du milieu comme objet de comparaison Si la valeur donnée est la clé du. enregistrement du milieu S'ils sont égaux, la recherche réussit ; si la valeur donnée est inférieure à la clé de l'enregistrement du milieu, la recherche continue dans la moitié gauche de l'enregistrement du milieu si la valeur donnée est supérieure à la clé de l'enregistrement du milieu ; enregistrement, la recherche se poursuit 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 :

<?php
//二分搜索(折半查找)算法(前提是数组必须是有序数组) 时间复杂度是 O(logn)
$i = 0; //存储对比的次数
//@param 待查找数组
//@param 待搜索的数字
function binsearch($arr,$num){
 $count = count($arr);
 $lower = 0;
 $high = $count - 1;
 global $i;
 while($lower <= $high){
  $i ++; //计数器
  if($arr[$lower] == $num){
   return $lower;
  }
  if($arr[$high] == $num){
   return $high;
  }
  $middle = intval(($lower + $high) / 2);
  if($num < $arr[$middle]){
   $high = $middle - 1;
  }else if($num > $arr[$middle]){
   $lower = $middle + 1;
  }else{
   return $middle;
  }
 }
 //返回-1表示查找失败
 return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = binsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

Résultat de l'exécution :

7
3

Résumé :

La complexité temporelle de la recherche binaire est O(logn). Cependant, étant donné que la condition préalable à la recherche binaire est le stockage séquentiel d'une table ordonnée (tableau), si la table ordonnée nécessite des opérations d'insertion ou de suppression fréquentes, le maintien du tri ordonné entraînera une charge de travail considérable.

Recommandations associées :

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

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

Exemple de code de recherche binaire PHP pour une implémentation récursive et non récursive

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!