php二分查找二种实现示例

/
  二分查找递归解法
  @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) ) );
}