Detaillierte Erläuterung und Beispiel-Tutorial des halben (binären) Suchalgorithmus von PHP

1. Einführung in den PHP-halben (binären) Suchalgorithmus

Die halbfache Suche (auch als binäre Suche bezeichnet) ist ein effizienter Algorithmus zum Auffinden von Zielelementen in einem geordneten Array. Der Algorithmus verengt den Suchbereich allmählich, indem er das Array kontinuierlich in zwei Hälften aufteilt und die Größe des Zielwerts mit dem Zwischenelement vergleicht, bis das Zielelement gefunden oder festgestellt wird, dass es nicht existiert.

1.1 Algorithmusprinzipien

Zu den Kernschritten der Klapp halbherstellung gehören:

1. Stellen Sie die Startposition des Arrays nach links und die Endposition nach rechts ein.

2. Berechnen Sie die Zwischenposition Mid = (links + rechts) / 2 .

3. Vergleichen Sie den Zielwert mit dem Zwischenpositionselement:

• Wenn gleich, wird die Mitte zurückgegeben und die Suche ist erfolgreich;
• Der Zielwert ist geringer als das mittlere Element, rechts auf Mitte - 1 eingestellt und weiter in der linken Hälfte suchen.
• Der Zielwert ist größer als das mittlere Element, links auf Mitte + 1 und suchen Sie weiter in der rechten Hälfte.

4. Wiederholen Sie die obigen Schritte, bis der Zielwert gefunden wurde oder links> rechts und die Suche fehlschlägt.

1.2 Algorithmus Beispiel

Der folgende PHP-Code implementiert den halbfindenden Suchalgorithmus:

 
function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    while ($left <= $right) {
        $mid = intval(($left + $right) / 2);
        if ($arr[$mid] == $target) {
            return $mid; // Gibt den Index des Zielwerts im Array zurück
        }
        if ($arr[$mid] < $target) {
            $left = $mid + 1; // Suchen Sie weiter auf der rechten Hälfte
        } else {
            $right = $mid - 1; // Suchen Sie weiter auf der linken Hälfte
        }
    }
    return -1; // Der Zielwert existiert nicht
}
<p>$arr = [1, 3, 5, 7, 9, 11, 15];<br>
$target = 7;<br>
$index = binarySearch($arr, $target);<br>
if ($index != -1) {<br>
echo "Zielwert $target Die Position im Array ist $index";<br>
} else {<br>
echo "Zielwert $target Existiert nicht im Array";<br>
}<br>

Der obige Code definiert die Funktion BinarySearch , die ein geordnetes Array- und Zielwert als Parameter empfängt, den Positionsindex des Zielwerts im Array zurückgibt und -1 zurückgibt, wenn er nicht vorhanden ist.

1.3 Algorithmusanalyse

Die zeitliche Komplexität der halbfindenden Suche ist O (logn) , wobei n die Arraylänge ist. Da jede Suche die Reichweite um die Hälfte reduziert, ist die Leistung viel besser als lineare Lookups, die für schnelle Positionierungselemente in großen geordneten Arrays geeignet sind.

2. Die Bedeutung von Algorithmen

2.1 Effiziente Suche in großen geordneten Arrays

Das Falten von halbfindeln wird die Suchzeit erheblich verkürzt, insbesondere wenn das Datenvolumen groß ist, kann die Zielelemente schnell lokalisieren und die Ineffizienz des Durchquerens des gesamten Arrays vermeiden.

2.2 Effizienz der Programmausführung verbessern

In Anwendungsszenarien, die häufige Suchvorgänge erfordern, kann die Verwendung von halbfinischen Suchvorgängen den gesamten Zeitaufwand des Programms verringern, den Ressourcenverbrauch verringern, die Reaktionsgeschwindigkeit und die Benutzererfahrung verbessern.

3. Zusammenfassung

In diesem Artikel wird die Prinzipien, die Implementierungscode und die Leistungsanalyse des PHP-Halbfindungs-Suchalgorithmus eingeführt. Die Mastering -binäre Suche ist besonders wichtig für die Entwicklung effizienter PHP -Anwendungen, die die Suchgeschwindigkeit effektiv verbessern und die Programmleistung optimieren können. Es wird empfohlen, dass Entwickler diesen Algorithmus verstehen und flexibel verwenden.