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 <= $subject[$mid] ) {
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)/2的方式是因為 防止low和high較大時候，產生溢出....
*/
//return round($low + ($high - $low) / 2);
/**
* 經過改進的插值算法求中值，當數值分布均勻情況下，再降低算法復雜度到lglgN
* 取中值算法2
*/
return round( (($key - $subject[$low]) / ($subject[$high] - $subject[$low])*($high-$low) ) );
}
