Explication détaillée des étapes de l'algorithme de recherche par interpolation de recherche par liste ordonnée PHP

Cette fois, je vais vous apporter une explication détaillée des étapes de l'algorithme de recherche par interpolation de recherche de table ordonnée PHP. Quelles sont les précautions de l'algorithme de recherche d'interpolation de recherche de table ordonnée PHP. Voici un cas pratique. , jetons un coup d'oeil.

Avant-propos :

Nous avons introduit la recherche binaire plus tôt, mais réfléchissons-y, pourquoi devons-nous l'intégrer moitié? ? Plutôt que de le plier en quatre ou plus ?

Par exemple, lorsque vous recherchez « pomme » dans un dictionnaire anglais, lorsque vous ouvrez le dictionnaire, vous tournez-vous inconsciemment vers la première page ou vers la dernière page ? Si vous cochez à nouveau « zoo », comment le vérifierez-vous ? Évidemment, vous ne commencez pas à chercher à partir du milieu du dictionnaire, mais vous regardez en avant ou en arrière dans un certain but.

De même, par exemple, si nous voulons trouver 5 dans un tableau avec 100 éléments dans la plage de valeurs de 0 à 10000 uniformément répartis du petit au grand, nous considérons naturellement d'abord le tableau l'indice est relativement petit. Commencez par paraître petit.

L'analyse ci-dessus est en fait l'idée de la recherche par interpolation, qui est une amélioration de la recherche binaire.

Idée de base :

Méthode de recherche basée sur la comparaison du mot-clé à trouver avec les mots-clés des enregistrements les plus grands et les plus petits de la recherche table , dont le noyau réside dans la formule de calcul d'interpolation. Regardons d'abord la formule de calcul de la moitié de la recherche :

La recherche d'interpolation consiste à en améliorer la moitié. et remplacez-le par le schéma de calcul suivant :

Le cœur de l'algorithme de recherche d'interpolation réside dans la formule de calcul d'interpolation :

$num - $arr[$inférieur]
——————————————
$arr[$high] - $arr[$inférieur]

Code :

<?php
//插值查找(前提是数组必须是有序数组) 事件复杂度　O(logn)
//但对于数组长度比较大，关键字分布又是比较均匀的来说，插值查找的效率比折半查找的效率高
$i = 0; //存储对比的次数
//@param 待查找数组
//@param 待搜索的数字
function insertsearch($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);
  $middle = intval($lower + ($num - $arr[$lower]) / ($arr[$high] - $arr[$lower]) * ($high - $lower)); 
  if($num < $arr[$middle]){
   $high = $middle - 1;
  }else if($num > $arr[$middle]){
   $lower = $middle + 1;
  }else{
   return $middle;
  }
 }
 return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = insertsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

Résumé :

D'un point de vue de la complexité temporelle, il est également O(logn), mais pour les tables de recherche avec des listes ordonnées relativement longues et une distribution relativement uniforme des mots-clés, les performances moyennes de l'algorithme de recherche par interpolation sont bien meilleures que la recherche binaire. Au contraire, si la distribution dans le tableau est similaire à {0, 1, 2, 2000, 2001,. . . 999998, 999999} Ce type de données extrêmement inégales, l'utilisation de la recherche par interpolation n'est peut-être pas un choix très approprié.

J'ai moi-même fait un exemple :

$arr = array(0,1,2,2000,2001,2002,2003,2004,5555,69666,99999,100000);
echo "位置：".binsearch($arr,5555);
echo "<br>";
echo "比较次数：".$i;
$i = 0; //重置比较次数
echo "<br>";
echo "位置：".insertsearch($arr,5555);
echo "<br>";
echo "比较次数：".$i;

Le résultat :

位置：8
比较次数：2
位置：8
比较次数：9

On peut obtenir que pour des données extrêmement inégales, l'efficacité de la recherche par interpolation est de moitié Trouvez bas.

PS : Pour la fonction binsearch() mentionnée ci-dessus vous pouvez vous référer à l'article précédent Recherche de table ordonnée PHP - recherche binaire (réduite de moitié)

Je crois que vous avez lu cet article Vous maîtrisez la méthode des cas. 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 des cas d'utilisation des connexions longues PHP

Comment implémenter l'exportation de données 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!