快捷導(dǎo)航

使用PHP實(shí)現(xiàn)二分查找算法代碼分享

更新時(shí)間：2011年06月24日 22:27:18 作者：

二分查找又稱折半查找，它是一種效率較高的查找方法。

第一種方法:
【二分查找要求】：1.必須采用順序存儲(chǔ)結(jié)構(gòu) 2.必須按關(guān)鍵字大小有序排列。　　
【優(yōu)缺點(diǎn)】折半查找法的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好;其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。　　
【算法思想】首先，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。

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

 
<?php 
//作者：遙遠(yuǎn)的期待 
//QQ:15624575 
//主頁：http://www.phptogether.com/ 
//正向排序的數(shù)組 
$arr=array(1,3,5,7,9,11); 
//逆向排序的數(shù)組 
$arr2=array(11,9,7,5,3,1); 
//對(duì)正向排序的數(shù)組進(jìn)行二分查找 
function searchpart($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);//這里只需要保證中間項(xiàng)下標(biāo)的計(jì)算值為整數(shù)即可，也可以四舍五入，不影響結(jié)果 
if($arr[$mid]>$x){//如果中間項(xiàng)的值大于待查值，說明代差值位于中間項(xiàng)的左邊，因此，起始下標(biāo)不變，結(jié)束下標(biāo)變成中間項(xiàng)下標(biāo)減1，第一次搜索的是$arr[0]-$arr[5]的話，下一次搜索 
$end=$mid-1;//$arr[0]-$arr[1] 
}elseif($arr[$mid]<$x){//如果中間項(xiàng)的值小于待查值，說明代差值位于中間項(xiàng)的右邊，因此，結(jié)束下標(biāo)不變，起始下標(biāo)變成中間項(xiàng)下標(biāo)加1，第一次搜索的是$arr[0]-$arr[5]的話，下一//次搜索是，$arr[3]-$arr[5] 
$start=$mid+1; 
}else{//找到了，返回待查值下標(biāo) 
return $mid; 
} 
} 
} 
//對(duì)逆向排序的數(shù)組進(jìn)行二分查找 
function searchpart2($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);//這里只需要保證中間項(xiàng)下標(biāo)的計(jì)算值為整數(shù)即可，也可以四舍五入，不影響結(jié)果 
if($arr[$mid]>$x){//如果中間項(xiàng)的值大于待查值，說明代差值位于中間項(xiàng)的右邊，因此，結(jié)束下標(biāo)不變，起始下標(biāo)變成中間項(xiàng)下標(biāo)加1，第一次搜索的是$arr[0]-$arr[5]的話，下一次搜索 
$start=$mid+1;//$arr[3]-$arr[5] 
}elseif($arr[$mid]<$x){//如果中間項(xiàng)的值小于待查值，說明代差值位于中間項(xiàng)的左邊，因此，起始下標(biāo)不變，結(jié)束下標(biāo)變成中間項(xiàng)下標(biāo)減1，第一次搜索的是$arr[0]-$arr[5]的話，下一//次搜索是，$arr[0]-$arr[1] 
$end=$mid-1; 
}else{//找到了，返回待查值下標(biāo) 
return $mid; 
} 
} 
} 
echo searchpart2($arr,5).'<br>'; 
echo searchpart2($arr2,5); 
?> 

PHP的二分查找算法實(shí)現(xiàn)
最近整理了下以前學(xué)習(xí)的算法知識(shí),雖然在WEB開發(fā)時(shí)算法用到的情況比較少,但還是把一些有用的算法做下備份。
折半查找法也稱為二分查找法，它充分利用了元素間的次序關(guān)系，采用分治策略，可在最壞的情況下用O(log n)完成搜索任務(wù)。
【基本思想】
將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如果x<a[n/2]，則我們只要在數(shù)組a的左半部繼續(xù)搜索x（這里假設(shè)數(shù)組元素呈升序排列）。如果x>a[n/2]，則我們只要在數(shù)組a的右半部繼續(xù)搜索x。
二分搜索法的應(yīng)用極其廣泛，而且它的思想易于理解。第一個(gè)二分搜索算法早在1946 年就出現(xiàn)了，但是第一個(gè)完全正確的二分搜索算法直到1962年才出現(xiàn)。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計(jì)算機(jī)專家不能在2小時(shí)內(nèi)寫出完全正確的二分搜索算法。問題的關(guān)鍵在于準(zhǔn)確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數(shù)的各種情況，其實(shí)整理后可以發(fā)現(xiàn)它的具體算法是很直觀的。
PHP的二分查找算法實(shí)現(xiàn)

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

 
/** 
* 二分查找算法 
* 
* @param array $arr 有序數(shù)組 
* @param int $val 查找的數(shù)值 
* @return int 查找值存在返回?cái)?shù)組下標(biāo),不存在返回-1 
*/ 
function binary_search($arr,$val) 
{ 
$l = count($arr);//獲得有序數(shù)組長度 
$low = 0; 
$high = $l -1; 
while($low <= $high) 
{ 
$middle = floor(($low + $high) / 2); 
if($arr[$middle] == $val) 
{ 
return $middle; 
} 
elseif($arr[$middle] > $val) 
{ 
$high = $middle - 1; 
} 
else 
{ 
$low = $middle + 1; 
} 
} 
return -1; 
} 
//示例 
$arr = array(1,2,3,4,5,6,7,8,9,12,23,33,35,56,67,89,99); 
echo binary_search($arr,57); 