PHP 二分探索アルゴリズムの例 [再帰的メソッドと非再帰的メソッド]

この記事の例では、PHP 二分探索アルゴリズムについて説明します。詳細は次のとおりです:

binarySearch

二分探索で使用される方法は、例としては比較的理解しやすいです:

① まず、真ん中の値を取得します。配列floor((low+top)/2),

②次に、求めたい数値と比較し、中間の値より大きい場合は、最初の値を中間の位置の次の位置に置き換えて続行します。最初のステップの操作; 中間の値より小さい場合は、最後の値を中間の値に置き換えます。前の位置に配置し、最初のステップを続行します

③ ターゲット番号が見つかるまで 2 番目のステップを繰り返します

例、1、3、9、23、54 から 23 という数字を見つけます。

最初の位置は 0、最後の位置は 4、中間の位置は 2 です。値は 9 で、23 より小さいので、最初の位置は 2+1 (3) に更新され、中間の位置は (3+4)/2=3 となり、比較的等しい 23 になります。つまり、

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

を求めます。

この記事が PHP プログラミングのすべての人に役立つことを願っています。

PHP バイナリ検索アルゴリズムの例 [再帰的メソッドと非再帰的メソッド] 関連記事をさらに詳しく知りたい場合は、PHP 中国語 Web サイトに注目してください。