php二分查找二種實(shí)現(xiàn)示例

更新時(shí)間：2014年03月12日 09:51:14 作者：

這篇文章主要介紹了php二分查找的二種實(shí)現(xiàn)示例，遞歸解法二分查找和非遞歸算法二分查找的示例,需要的朋友可以參考下

php二分查找示例

二分查找常用寫(xiě)法有遞歸和非遞歸，在尋找中值的時(shí)候，可以用插值法代替求中值法。
當(dāng)有序數(shù)組中的數(shù)據(jù)均勻遞增時(shí)，采用插值方法可以將算法復(fù)雜度從中值法的lgN減小到lglgN

復(fù)制代碼代碼如下:

/**
* 二分查找遞歸解法
* @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較大時(shí)候，產(chǎn)生溢出....
*/
//return round($low + ($high - $low) / 2);

/**
* 經(jīng)過(guò)改進(jìn)的插值算法求中值，當(dāng)數(shù)值分布均勻情況下，再降低算法復(fù)雜度到lglgN
* 取中值算法2
*/
return round( (($key - $subject[$low]) / ($subject[$high] - $subject[$low])*($high-$low) ) );
}

您可能感興趣的文章:

相關(guān)文章

thinkPHP框架實(shí)現(xiàn)類(lèi)似java過(guò)濾器的簡(jiǎn)單方法示例
這篇文章主要介紹了thinkPHP框架實(shí)現(xiàn)類(lèi)似java過(guò)濾器的簡(jiǎn)單方法,結(jié)合實(shí)例形式分析了thinkPHP基于繼承實(shí)現(xiàn)的登錄驗(yàn)證功能相關(guān)操作方法,需要的朋友可以參考下
2018-09-09
tp5.1 框架路由操作-URL生成實(shí)例分析
這篇文章主要介紹了tp5.1 框架路由操作-URL生成,結(jié)合實(shí)例形式分析了tp5.1 框架針對(duì)路由操作URL生成的相關(guān)實(shí)現(xiàn)原理、操作技巧與注意事項(xiàng),需要的朋友可以參考下
2020-05-05
PHP讀取漢字的點(diǎn)陣數(shù)據(jù)
本文給大家詳細(xì)講述了使用PHP讀取漢字的點(diǎn)陣數(shù)據(jù)的方法和示例，十分的實(shí)用，有需要的小伙伴可以參考下。
2015-06-06
PHP通用分頁(yè)類(lèi)page.php[仿google分頁(yè)]
PHP通用分頁(yè)類(lèi)。本代碼是用于分頁(yè)用的，稍做修改可用于各種程序。使用方式請(qǐng)參考本人文章。
2008-08-08
PHP將URL轉(zhuǎn)換成短網(wǎng)址的算法分享
短網(wǎng)址（Short URL）顧名思義就是在形式上比較短的網(wǎng)址。在Web 2.0的今天，不得不說(shuō)這是一個(gè)潮流。目前已經(jīng)有許多類(lèi)似服務(wù)，借助短網(wǎng)址您可以用簡(jiǎn)短的網(wǎng)址替代原來(lái)冗長(zhǎng)的網(wǎng)址，讓使用者可以更容易的分享鏈接,下面來(lái)看看如何用PHP實(shí)現(xiàn)這個(gè)功能，有需要的朋友們可以參考。
2016-09-09
Laravel 5.5中為響應(yīng)請(qǐng)求提供的可響應(yīng)接口詳解
這篇文章主要給大家介紹了關(guān)于Laravel 5.5中為響應(yīng)請(qǐng)求提供的可響應(yīng)接口的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。
2017-11-11
PHP驗(yàn)證信用卡卡號(hào)是否正確函數(shù)
這篇文章主要介紹了PHP驗(yàn)證信用卡卡號(hào)是否正確函數(shù),本文直接給出實(shí)現(xiàn)代碼,需要的朋友可以參考下
2015-05-05
詳解使用php-cs-fixer格式化代碼
這篇文章主要介紹了使用php-cs-fixer格式化代碼,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2020-09-09
Laravel中Facade的加載過(guò)程與原理詳解
Facade其實(shí)是一個(gè)容器中類(lèi)的靜態(tài)代理，他可以讓你以靜態(tài)的方式來(lái)調(diào)用存放在容器中任何對(duì)象的任何方法，下面這篇文章主要給大家介紹了關(guān)于Laravel中Facade的加載過(guò)程與原理的相關(guān)資料，需要的朋友可以參考下。
2017-09-09
CodeIgniter框架URL路由總結(jié)
這篇文章主要介紹了CodeIgniter框架URL路由總結(jié),本文也以作為CodeIgniter路由入門(mén)教程,講解了配置規(guī)則的幾個(gè)方面,需要的朋友可以參考下
2014-09-09