时时商务社区

标题: php二分查找二种实现示例 [打印本页]

作者: xgnic 时间: 2018-2-14 05:59

         php二分查找示例
二分查找常用写法有递归和非递归，在寻找中值的时候，可以用插值法代替求中值法。
当有序数组中的数据均匀递增时，采用插值方法可以将算法复杂度从中值法的lgN减小到lglgN
[U]复制代码[/U] 代码如下:
/**
* 二分查找递归解法
* @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
/**
* 二分查找的非递归算法
* @param type $subject
* @param type $n
* @param type $key
*/
function binarySearch_nr($subject, $n, $key)
{
$low = 0;
$high = $n;
while ( $low  $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实现二分查找算法代码分享

PHP 冒泡排序二分查找顺序查找二维数组排序算法函数的详解

PHP二分查找算法示例【递归与非递归方法】

PHP二分查找算法的实现方法示例

PHP实现的折半查找算法示例

PHP常用的排序和查找算法

php数据结构与算法(PHP描述) 查找与二分法查找

php数据结构之顺序链表与链式线性表示例

php线性表的入栈与出栈实例分析

php线性表顺序存储实现代码(增删查改)

PHP有序表查找之二分查找（折半查找）算法示例

欢迎光临时时商务社区 (http://bbs.4435.cn/)