Explication détaillée du cas de l'algorithme de demi-recherche PHP

Cette fois, je vais vous apporter une explication détaillée du cas de l'algorithme de demi-recherche PHP. Quelles sont les précautions lors de l'utilisation de la demi-recherche PHP. Voici un cas pratique, jetons un coup d'œil.

Introduction :

Recherche binaire technologie, é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ésumé :

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.

Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez prêter attention aux autres articles connexes sur le site Web chinois de php !

Lecture recommandée :

Analyse du cas d'utilisation des connexions longues PHP

Explication détaillée de l'utilisation de la conteneurisation et du déploiement des applications PHP

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!