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

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

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

php二分查找示例

二分查找常用寫法有遞歸和非遞歸，在尋找中值的時候，可以用插值法代替求中值法。
當有序數(shù)組中的數(shù)據(jù)均勻遞增時，采用插值方法可以將算法復雜度從中值法的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較大時候，產(chǎn)生溢出....
*/
//return round($low + ($high - $low) / 2);

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

您可能感興趣的文章:

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