PHP 二分法検索
二分法の考え方は次のとおりです。配列を与えて、配列の先頭と末尾のインデックスを加算して 2 で割ります。このようにして、探している数値の値を比較します。中間のインデックス位置の値を使用します
それらが等しい場合、中間位置のインデックスを返します。 中間位置の値が探している値より大きい場合は、中間位置のインデックスを末尾として使用します。
中間位置の値が探している値よりも小さい場合は、中間位置のインデックスをヘッド インデックスとして使用し、それをヘッド インデックスに追加して 2 で割ります。次に、それを末尾のインデックスに追加し、2 で割って中央のインデックスの比較を取得します。このループは、
<?php $arr = array(1,2,3,4,5,6,7,8,9); print_r(binarySearch($arr,9)); function binarySearch($arr,$Num){ $StartPos=0; $EndPos = count($arr)-1; $m = (int)(($EndPos+$StartPos)/2); while($arr[$m]!=$Num){ if($arr[$m] == $Num){ break; }else if($arr[$m] < $Num){ $StartPos = (int)$m; if($m+$EndPos>(2*$m)){ $m= (int)(($m+$EndPos)/2)+1; } }else if($arr[$m] > $Num){ $EndPos = (int)$m; $m= (int)(($m+$StartPos)/2); } } return $m; } ?>