php二分查找二种实现示例
php二分查找二种实现示例
发布时间:2016-12-29 来源:查字典编辑
摘要: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教程学习
热门php教程学习
编程开发子分类