close

Binärer Suchalgorithmus (Binary Search) in PHP: Erklärung, Schritte und Beispiel

Der binäre Suchalgorithmus ist eine effiziente Methode, um einen bestimmten Wert in einem sortierten Array zu finden. Dieser Ansatz unterteilt das Array in kleinere Teile und vergleicht kontinuierlich den Wert an der mittleren Position des Suchbereichs mit dem Zielwert. Stimmen die Werte überein, ist der gesuchte Wert gefunden; andernfalls grenzt der Algorithmus den Suchbereich weiter ein und wiederholt den Vorgang, bis der Wert gefunden wird oder keine weiteren Elemente mehr zur Untersuchung vorhanden sind.

Schritte:

  1. Initialisieren Sie den Suchbereich: Wählen Sie zunächst den Suchbereich von der ersten left  bis zur letzten Position right  des Arrays aus.
  2. Finden Sie den Mittelpunkt: Berechnen Sie den Mittelpunkt, indem Sie die left rechten Positionen mitteln. Dies ist der Mittelpunkt des Suchbereichs.
  3. Werte vergleichen: Vergleichen Sie den Wert am Mittelpunkt mit dem Zielwert.
  4. Vergleichsergebnis verarbeiten: Wenn der Wert am Mittelpunkt mit dem Zielwert übereinstimmt, wird diese Position zurückgegeben. Wenn der Wert am Mittelpunkt kleiner als der Zielwert ist, aktualisieren Sie die linke Position auf Mitte + 1, um die rechte Hälfte zu durchsuchen. Wenn der Wert am Mittelpunkt größer als der Zielwert ist, aktualisieren Sie die rechte Position auf Mitte- 1, um die linke Hälfte zu durchsuchen.
  5. Wiederholen: Wiederholen Sie die Schritte 2 bis 4, bis der Wert gefunden wurde oder keine weiteren Elemente zu überprüfen sind left > right.

Vorteile und Nachteile

Vorteile:

  • Effiziente Leistung: Die zeitliche Komplexität des Algorithmus beträgt O(log n), was ihn für die Verarbeitung großer Datenmengen äußerst effizient macht.
  • Effektiv für große Datenmengen: Die binäre Suche reduziert effektiv die Anzahl der Elemente, die bei großen Datenmengen schnell untersucht werden müssen.

Nachteile:

  • Gilt nur für sortierte Arrays: Der Algorithmus funktioniert nur für sortierte Arrays.
  • Variable Anzahl von Schritten: Die Anzahl der Schritte, die erforderlich sind, um den Wert zu finden, hängt von seiner Position im Array ab und kann für Werte nahe den Enden viele Schritte erfordern.

Beispiel: Binäre Suche zum Finden des Werts 12 in einem sortierten Array in PHP 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

Erläuterung des Beispiels

  1. Wir beginnen mit dem anfänglichen Suchbereich von der ersten left = 0 bis zur letzten Position right = 6  des Arrays.
  2. Wir berechnen den Mittelpunkt(Mitte), indem wir die linke und rechte Position mitteln; mid = 3. Der Wert in der Mitte beträgt 12.
  3. Wir vergleichen den Wert bei mid(12) mit dem Zielwert(12) und finden eine Übereinstimmung, also geben wir Position 3 zurück.
  4. Der Algorithmus endet und wir geben das Ergebnis „Wert 12 an Position 3 gefunden“ aus.