Recherche de liste ordonnée PHP ---- recherche par interpolation

Avant-propos :

Nous avons introduit la recherche binaire plus tôt, mais réfléchissons-y, pourquoi devons-nous la faire en deux ? Au lieu 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 uniformément répartis du plus petit au plus grand dans la plage de valeurs de 0 à 10 000, nous commençons naturellement la recherche en considérant d'abord l'indice le plus petit du tableau. .

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 :

La méthode de recherche est basée sur la comparaison du mot-clé à rechercher avec les mots-clés des enregistrements les plus grands et les plus petits de la table de recherche. Le cœur de celle-ci réside dans l'interpolation. formule de calcul :
$key - $arr[$low]
——————————-
$arr[$high] - $arr[$low]

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é :

Du point de vue de la complexité temporelle, c'est aussi O(logn), mais il est plus long pour les listes ordonnées, et le La distribution des mots clés est relativement uniforme pour les tables de recherche, les performances moyennes de l'algorithme de recherche par interpolation sont bien meilleures que celles de 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é.

Ce qui précède est le contenu de la recherche de table ordonnée PHP ---- recherche par interpolation Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn) !