php二分查找二種實(shí)現(xiàn)示例
php二分查找示例
二分查找常用寫法有遞歸和非遞歸,在尋找中值的時候,可以用插值法代替求中值法。
當(dāng)有序數(shù)組中的數(shù)據(jù)均勻遞增時,采用插值方法可以將算法復(fù)雜度從中值法的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的方式是因?yàn)?防止low和high較大時候,產(chǎn)生溢出....
*/
//return round($low + ($high - $low) / 2);
/**
* 經(jīng)過改進(jìn)的插值算法求中值,當(dāng)數(shù)值分布均勻情況下,再降低算法復(fù)雜度到lglgN
* 取中值算法2
*/
return round( (($key - $subject[$low]) / ($subject[$high] - $subject[$low])*($high-$low) ) );
}
- 使用PHP實(shí)現(xiàn)二分查找算法代碼分享
- PHP 冒泡排序 二分查找 順序查找 二維數(shù)組排序算法函數(shù)的詳解
- php二分法在IP地址查詢中的應(yīng)用
- 深入理解PHP幾個算法:PHP冒泡、PHP二分法、PHP求素數(shù)、PHP乘法表
- PHP字符串逆序排列實(shí)現(xiàn)方法小結(jié)【strrev函數(shù),二分法,循環(huán)法,遞歸法】
- php順序查找和二分查找示例
- php 數(shù)組二分法查找函數(shù)代碼
- php數(shù)據(jù)結(jié)構(gòu)與算法(PHP描述) 查找與二分法查找
- php中二分法查找算法實(shí)例分析
- 數(shù)據(jù)結(jié)構(gòu)之利用PHP實(shí)現(xiàn)二分搜索樹
相關(guān)文章
php與java通過socket通信的實(shí)現(xiàn)代碼
PHP通過socket與java進(jìn)行通信與基本的sockent編程沒什么區(qū)別,一個讀,一個寫,只是方便起見,用java寫,PHP讀2013-10-10Yii2實(shí)現(xiàn)UploadedFile上傳文件示例
這篇文章主要介紹了Yii2實(shí)現(xiàn)UploadedFile上傳文件示例的資料,這里整理了詳細(xì)的代碼,有需要的小伙伴可以參考下。2017-02-02PHP解析html類庫simple_html_dom的轉(zhuǎn)碼bug
這篇文章主要介紹了PHP解析html類庫simple_html_dom的轉(zhuǎn)碼bug ,需要的朋友可以參考下2014-05-05