PHP-geordnete Listensuche ---- Interpolationssuche

Vorwort:

Wir haben die binäre Suche früher eingeführt, aber denken wir mal darüber nach: Warum müssen wir sie halbieren? Anstatt es in ein Viertel oder mehr zu falten?

Wenn Sie beispielsweise in einem englischen Wörterbuch nach „Apple“ suchen und das Wörterbuch öffnen, blättern Sie dann unbewusst zur Titelseite oder zur Rückseite? Wenn Sie „Zoo“ noch einmal ankreuzen, wie werden Sie es dann überprüfen? Offensichtlich fängt man nicht in der Mitte des Wörterbuchs an, nach oben zu schauen, sondern man blickt mit einem bestimmten Ziel vorwärts oder rückwärts.

Wenn wir beispielsweise in einem Array mit 100 Elementen, die gleichmäßig von klein nach groß im Wertebereich von 0 bis 10000 verteilt sind, 5 finden möchten, beginnen wir die Suche natürlich zunächst mit der Betrachtung des kleineren Array-Index .

Die obige Analyse ist eigentlich die Idee der Interpolationssuche, die eine Verbesserung der binären Suche darstellt.

Grundidee:

Die Suchmethode basiert auf dem Vergleich des zu durchsuchenden Schlüsselwortschlüssels mit den Schlüsselwörtern der größten und kleinsten Datensätze in der Nachschlagetabelle. Der Kern liegt in der Interpolation Berechnungsformel:
$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;

Zusammenfassung:

Aus Sicht der Zeitkomplexität ist es auch O(logn), aber es ist länger für geordnete Listen und die Die Schlüsselwortverteilung ist relativ gleichmäßig. Bei Nachschlagetabellen ist die durchschnittliche Leistung des Interpolationssuchalgorithmus viel besser als die der binären Suche. Im Gegenteil, wenn die Verteilung im Array ähnlich ist wie {0, 1, 2, 2000, 2001,. . . 999998, 999999} Für diese Art extrem ungleichmäßiger Daten ist die Verwendung der Interpolationssuche möglicherweise keine sehr geeignete Wahl.

Das Obige ist der Inhalt der PHP-geordneten Tabellensuche ---- Interpolationssuche. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn).