Binäre Suche in PHP

Was ist binäre Suche?

Binäre Suche ist ein Suchalgorithmus, der verwendet wird, um die Position eines Zielwerts in einem sortierten Array (oder einer Liste) effizient zu finden. Dabei wird der Suchbereich wiederholt in zwei Hälften geteilt und das mittlere Element mit dem Zielwert verglichen.

Der binäre Suchalgorithmus folgt den folgenden Schritten:

• Beginnen Sie mit dem gesamten sortierten Array.

• Setzen Sie den linken Zeiger auf das erste Element des Arrays und den rechten Zeiger auf das letzte Element.

• Berechnen Sie den mittleren Index als Durchschnitt des linken und rechten Zeigers (ganzzahlige Division).

• Vergleichen Sie den Wert am mittleren Index mit dem Zielwert.

• Wenn der Zwischenwert gleich dem Zielwert ist, ist die Suche erfolgreich und der Algorithmus gibt den Index zurück.

• Wenn der Zielwert größer als der Mittelwert ist, eliminieren Sie die linke Hälfte des Suchbereichs, indem Sie den linken Zeiger auf Mitte + 1 aktualisieren.

• Wenn der Zielwert kleiner als der Mittelwert ist, eliminieren Sie die rechte Hälfte des Suchbereichs, indem Sie den rechten Zeiger auf die Mitte aktualisieren – 1.

• Wiederholen Sie die Schritte 3 bis 7, bis der Zielwert gefunden wurde oder der Suchbereich leer ist (der linke Zeiger ist größer als der rechte Zeiger).

• Wenn der Suchbereich leer ist und der Zielwert nicht gefunden wird, schließt der Algorithmus, dass der Zielwert nicht im Array vorhanden ist, und gibt -1 oder einen entsprechenden Hinweis zurück.

Die binäre Suche ist ein sehr effizienter Algorithmus mit einer Zeitkomplexität von O(log n), wobei n die Anzahl der Elemente im Array ist. Dies ist besonders effektiv für große sortierte Arrays, da es den Suchbereich schnell einschränkt, indem es ihn bei jedem Schritt in zwei Hälften teilt, was eine schnelle Suche auch bei einer großen Anzahl von Elementen ermöglicht.

Binäres Such-PHP-Programm

Methode 1 – Iteration verwenden

Beispiel

<?php
function binarySearch($arr, $target) {
   $left = 0;
   $right = count($arr) - 1;
   while ($left <= $right) {
      $mid = floor(($left + $right) / 2);
      // Check if the target value is found at the middle index
      if ($arr[$mid] === $target) {
         return $mid;
      }
      // If the target is greater, ignore the left half
      if ($arr[$mid] < $target) {
         $left = $mid + 1;
      }
      // If the target is smaller, ignore the right half
      else {
         $right = $mid - 1;
      }
   }
   // Target value not found in the array
   return -1;
}
// Example usage 1
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 91;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.<br>";
} else {
   echo "Target value found at index $resultIndex.<br>";
}
// Example usage 2
$targetValue = 42;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.";
} else {
   echo "Target value found at index $resultIndex.";
}
?>

Ausgabe

Target value found at index 9.
Target value not found in the array.

Methode 2 – Rekursion verwenden

Beispiel

<?php
function binarySearchRecursive($arr, $target, $left, $right) {
   if ($left > $right) {
      // Target value not found in the array
      return -1;
   }
   $mid = floor(($left + $right) / 2);
   // Check if the target value is found at the middle index
   if ($arr[$mid] === $target) {
      return $mid;
   }
   // If the target is greater, search the right half
   if ($arr[$mid] < $target) {
      return binarySearchRecursive($arr, $target, $mid + 1, $right);
   }
   // If the target is smaller, search the left half
   return binarySearchRecursive($arr, $target, $left, $mid - 1);
}
// Wrapper function for the recursive binary search
function binarySearch($arr, $target) {
   $left = 0;
   $right = count($arr) - 1;
   return binarySearchRecursive($arr, $target, $left, $right);
}
// Example usage
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 16;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.";
} else {
   echo "Target value found at index $resultIndex.";
}
?>

Ausgabe

Target value found at index 4.

Fazit

Zusammenfassend ist die binäre Suche ein leistungsstarker Algorithmus, der einen Zielwert in einem sortierten Array effizient finden kann. Es bietet zwei gängige Implementierungen: iterativ und rekursiv. Die iterative Methode verwendet eine While-Schleife, um den Suchbereich wiederholt in zwei Hälften zu teilen, bis der Zielwert gefunden wird oder der Bereich leer wird. Die Implementierung ist einfach und eignet sich perfekt für die meisten Szenarien. Andererseits verwenden rekursive Methoden rekursive Funktionen, um binäre Suchen durchzuführen. Es folgt der gleichen Logik wie die iterative Methode, verwendet jedoch Funktionsaufrufe anstelle von Schleifen. Die rekursive binäre Suche bietet eine sauberere Implementierung, kann jedoch aufgrund der Manipulation des Funktionsaufrufstapels einen etwas höheren Overhead verursachen. Insgesamt bieten beide Methoden eine effiziente und zuverlässige Möglichkeit, binäre Suchvorgänge durchzuführen.

Das obige ist der detaillierte Inhalt vonBinäre Suche in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!