PHPバイナリサーチの2つの実装例_PHPチュートリアル

if ( $start >= $end ) return FALSE;
$mid = getMidKey($subject, $start, $end, $key);
if ( $subject[$mid] == $key ) return $mid ;
if ( $key > $subject[$mid] ) {
return binarySearch($subject, $mid, $end, $key);
}
if ( $key return binarySearch($subject, $start, $mid, $key);
}
}

/**
* 二分探索のための非再帰アルゴリズム
* @param type $subject
* @param type $n
* @param type $key
*/
function binarySearch_nr($subject, $n, $key)
{
$low = 0;
$high = $n;
while ( $low <= $high ) {
$mid = getMidKey($subject, $low, $high, $key);
if ( $subject[$mid] == $key ) return $mid;
if ( $subject[$mid] < $key ) {
$low = $mid + 1;
}
if ( $subject[$mid] > $key ) {
$high = $mid - 1;
}
}
}
function getMidKey($subject, $ low, $high, $key)
{
/**
* 中央値アルゴリズム 1 は、low と high が大きい場合のオーバーフローを防ぐために ($low+$high)/2 メソッドを使用しません....
*/
//returnround($low + ($high - $low) / 2);

/**
* 改良された内挿アルゴリズムは中央値を見つけます。数値分布が均一な場合、アルゴリズムの複雑さは lglgN に軽減されます
* 中央値アルゴリズム 2
*/
returnround( (($key - $subject[$low]) / ($subject[$high] - $subject[$low])*($high-$low) ) );
}