PHP-geordnete Listensuche ----Binäre Suche (halb)

Einführung:

Binäre Suchtechnologie, auch als Halbsuche bekannt. Seine Voraussetzung ist, dass die Datensätze in der linearen Tabelle in der Schlüsselreihenfolge vorliegen müssen (normalerweise in der Reihenfolge von klein nach groß) und die lineare Tabelle sequentiell gespeichert werden muss.

Grundidee:

Nehmen Sie in einer geordneten Liste den mittleren Datensatz als Vergleichsobjekt. Wenn der angegebene Wert dem Schlüssel des mittleren Datensatzes entspricht, ist die Suche erfolgreich Der angegebene Wert ist kleiner als der mittlere Datensatz. Wenn der angegebene Wert größer als das Schlüsselwort des mittleren Datensatzes ist, wird die Suche in der linken Hälfte des mittleren Datensatzes fortgesetzt. Wenn der angegebene Wert größer als das Schlüsselwort des mittleren Datensatzes ist, wird die Suche fortgesetzt Die Suche wird in der rechten Hälfte des mittleren Datensatzes fortgesetzt. Wiederholen Sie den obigen Vorgang, bis die Suche erfolgreich ist oder kein Datensatz in allen Suchbereichen vorhanden ist und die Suche fehlschlägt.

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;

Zusammenfassung:

Die zeitliche Komplexität der binären Suche beträgt O(logn). Da die Voraussetzung für die binäre Suche jedoch die sequentielle Speicherung einer geordneten Tabelle (Array) ist, wird die Aufrechterhaltung der geordneten Sortierung einen erheblichen Arbeitsaufwand mit sich bringen, wenn die geordnete Tabelle häufige Einfüge- oder Löschvorgänge erfordert.

Das Obige ist der Inhalt der PHP-geordneten Tabellensuche – binäre Suche (halbiert). Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn).