Beispiel für einen binären PHP-Suchalgorithmus [rekursive und nicht rekursive Methoden]

Das Beispiel in diesem Artikel beschreibt den PHP-Binärsuchalgorithmus. Teilen Sie es als Referenz mit allen:

binarySearch

Die von der binären Suche verwendete Methode ist relativ einfach zu verstehen:

① Nehmen Sie zuerst den Wert unten in der Mitte des Arrays ((niedrig+oben)/2),

② Vergleichen Sie ihn dann mit der Zahl, die Sie finden müssen, wenn er größer als der mittlere Wert ist , Ersetzen Sie den ersten Wert durch die nächste Position in der Mitte und fahren Sie mit dem ersten Schritt fort. Wenn er kleiner als der mittlere Wert ist, ersetzen Sie den Endwert durch die Position über der mittleren Position und fahren Sie mit dem ersten Schritt fort

③ Wiederholen Sie den zweiten Schritt, bis die Zielnummer gefunden ist

Suchen Sie beispielsweise die Nummer 23 aus 1, 3, 9, 23, 54. Die erste Position von

ist 0, die Die letzte Position ist 4 und die mittlere Position ist 2. Wenn der Wert 9 ist, was kleiner als 23 ist, wird die erste Position auf 2 aktualisiert. +1 ist 3, dann ist die mittlere Position (3+4)/2= 3, und der Wert ist 23. Wenn sie gleich sind, können wir

//  非递归算法：
//  $target是要查找的目标 $arr是已经排序好的数组
function binary(&$arr,$low,$top,$target){
    while($low <= $top){
//由于php取商是有小数的，所以向下取整，不过也可不加，数组也会取整
      $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;
}

//  递归算法：
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;
    }
}

Ich hoffe, dieser Artikel wird für jeden in der PHP-Programmierung hilfreich sein.

Weitere Artikel zu PHP-Binärsuchalgorithmen [rekursive und nicht rekursive Methoden] finden Sie auf der chinesischen PHP-Website!