PHPバイナリサーチの2つの実装例_PHPチュートリアル
- WBOYオリジナル
- 2016-07-13 10:36:01885ブラウズ
phpバイナリ検索の例
二分探索で一般的に使用される記述方法は、再帰的および非再帰的です。中央値を求める場合、中央値法の代わりに内挿法を使用できます。
順序付けされた配列内のデータが均一に増加する場合、内挿法を使用してアルゴリズムの複雑さを中央値法の lgN から lglgN に削減できます
/**
* 二分探索再帰解法
* @param type $subject
* @param type $start
* @param type $end
* @param type $key
* @return boolean
*/
function binarySearch_r($subject, $start, $end, $key)
{
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) ) );
}