php二分查找示例

二分查找常用寫法有遞歸和非遞歸，在尋找中值的時(shí)候，可以用插值法代替求中值法。
當(dāng)有序數(shù)組中的數(shù)據(jù)均勻遞增時(shí)，采用插值方法可以將算法復(fù)雜度從中值法的lgN減小到lglgN

復(fù)制代碼 代碼如下:
/**
 * 二分查找遞歸解法
 * @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的方式是因?yàn)?防止low和high較大時(shí)候，產(chǎn)生溢出....
  */
 //return round($low + ($high - $low) / 2);

 /**
  * 經(jīng)過改進(jìn)的插值算法求中值，當(dāng)數(shù)值分布均勻情況下，再降低算法復(fù)雜度到lglgN
  * 取中值算法2
  */
 return round( (($key - $subject[$low]) / ($subject[$high] - $subject[$low])*($high-$low) ) );
}

php技術(shù)：php二分查找二種實(shí)現(xiàn)示例，轉(zhuǎn)載需保留來源！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。