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

上述就是小编为大家分享的php中实现二分查找算法的方式有哪些了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注亿速云行业资讯频道。