Beispielerklärung des in PHP implementierten binären Suchalgorithmus

Dieser Artikel stellt hauptsächlich den in PHP implementierten Halbsuchalgorithmus vor, beschreibt kurz das Prinzip der Halbsuche und analysiert die damit verbundenen Betriebsfähigkeiten von PHP unter Verwendung rekursiver und nicht rekursiver Methoden zur Implementierung des Halbsuchalgorithmus im Formular von Beispielen. Freunde, die es brauchen, können als Referenz

Das Beispiel in diesem Artikel beschreibt den in PHP implementierten Halbsuchalgorithmus. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Definition: Halbsuchtechnologie, also binäre Suche. Seine Voraussetzung ist, dass die Datensätze in der linearen Tabelle in der Schlüsselreihenfolge vorliegen müssen (normalerweise von groß nach klein) und die lineare Tabelle sequentiell gespeichert werden muss.

Die Grundidee der Halbsuche: Nehmen Sie den mittleren Datensatz als Vergleichsobjekt. Wenn der angegebene Wert das Schlüsselwort des mittleren Datensatzes ist, ist das Schlüsselwort des mittleren Datensatzes gleich, dann ist die Suche erfolgreich; wenn der angegebene Wert kleiner als der Schlüssel des mittleren Datensatzes ist, wird die Suche fortgesetzt. Wenn der angegebene Wert größer als der Schlüssel des mittleren Datensatzes ist, wird die Suche 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.

Implementierungscode:

<?php
//递归方式
function bin_recur_search($arr,$val){
  global $time;
  if(count($arr) >= 1){
    $mid = intval(count($arr) / 2);
    $time++;
    if($arr[$mid] == $val){
      return &#39;值为:&#39;.$arr[$mid].&#39;<br>查找次数：&#39;.$time.&#39;<br>&#39;;
    }elseif($arr[$mid] > $val){
      $arr = array_splice($arr,0,$mid);
      return bin_recur_search($arr, $val);
    }else{
      $arr = array_slice($arr,$mid + 1);
      return bin_recur_search($arr, $val);
    }
  }
  return &#39;未找到&#39;.$val;
}
//非递归方式
function bin_search($arr,$val){
  if(count($arr) >= 1){
    $low = 0;
    $high = count($arr);
    $time = 0;
    while($low <= $high){
      $time++;
      $mid = intval(($low + $high)/2);
      if($val == $arr[$mid]){
        return &#39;索引：&#39;.$mid.&#39;<br>值为：&#39;.$arr[$mid].&#39;<br>查找次数：&#39;.$time;
      }elseif($val > $arr[$mid]){
        $low = $mid + 1;
      }else{
        $high = $mid - 1;
      }
    }
  }
  return &#39;未找到&#39;.$val;
}
$arr = array(1,3,5,7,7,9,25,68,98,145,673,8542);
echo bin_recur_search($arr, 673);
echo bin_search($arr, 673);
?>

Laufergebnis:

值为:673
查找次数：4
索引：10
值为：673
查找次数：4

Artikel, die Sie interessieren könnten:

Beispiel für einen in PHP implementierten String-Matching-Algorithmus

Erläuterung des in PHP implementierten Maximum-Forward-Matching-Algorithmus

Installation und Verwendung des PHP-Performance-Analysetools xhprof und zugehörige Vorsichtsmaßnahmen

Das obige ist der detaillierte Inhalt vonBeispielerklärung des in PHP implementierten binären Suchalgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!