php二分查找二种实现示例

php二分查找二种实现示例

 这篇文章主要介绍了php二分查找的二种实现示例，递归解法二分查找和非递归算法二分查找的示例,需要的朋友可以参考下

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) ) ); }