PHP-Implementierung eines Beispielcodes für die binäre Suche

Binäre Suche, auch als halbe Suche bekannt, hat den Vorteil weniger Vergleiche, eine schnelle Suchgeschwindigkeit und eine gute durchschnittliche Leistung. Der Nachteil besteht darin, dass die nachzuschlagende Tabelle geordnet sein muss Tabelle und EinfügenLöschenSchwierig. Daher eignet sich die binäre Suchmethode für geordnete Listen, die sich nicht häufig ändern, aber häufig durchsucht werden. Unter der Annahme, dass die Elemente in der Tabelle in aufsteigender Reihenfolge angeordnet sind, vergleichen Sie zunächst das in der mittleren Position der Tabelle aufgezeichnete Schlüsselwort mit dem Suchschlüsselwort. Wenn die beiden gleich sind, ist die Suche erfolgreich. Andernfalls wird der Datensatz in der mittleren Position verwendet Teilen Sie die Tabelle in zwei Untertabellen, die erste und die letzte. Wenn das in der mittleren Position aufgezeichnete Schlüsselwort größer als das Suchschlüsselwort ist, wird die vorherige Untertabelle weiter durchsucht, andernfalls wird die nächste Untertabelle durchsucht weiter. Wiederholen Sie den obigen Vorgang, bis ein Datensatz gefunden wird, der die Bedingungen erfüllt, wodurch die Suche erfolgreich ist, oder bis die Untertabelle nicht mehr vorhanden ist. In diesem Fall schlägt die Suche fehl.

Schleife

function binary(&$arr,$low,$top,$target){
    while($low <= $top){        $mid = floor(($low+$top)/2);        echo $mid."<br>";        if($arr[$mid]==$target){            return $arr[$mid];
        }elseif($arr[$mid]<$target){            $low = $mid+1;                
        }else{            $top = $mid-1;
        }
    }    return -1;
}

Rekursion

function binaryRecursive(&$arr,$low,$top,$target){
    if($low<=$top){        $mid = floor(($low+$top)/2);        if($mid==$target){            return $arr[$mid];
        }elseif($arr[$mid]<$target){            return binaryRecursive($arr,$mid+1,$top,$target);
        }else{            return binaryRecursive($arr,$low,$top-1,$target);
        }
    }else{        return -1;
    }
}

Hinweis: Die Voraussetzung der binären Suche ist Array In der richtigen Reihenfolge anordnen

Das obige ist der detaillierte Inhalt vonPHP-Implementierung eines Beispielcodes für die binäre Suche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!