使用PHP實現二分查找演算法程式碼分享

第一種方法: 
【二分查找要求】：1.必須採用順序儲存結構 2.必須依關鍵字大小有序排列。 　　 
【優缺點】折半查找法的優點是比較次數少，查找速度快，平均性能好;其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
【演算法思想】首先，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於尋找關鍵字，則進一步尋找前一子表，否則進一步尋找後一子表。 

<?php 
//正向排序的数组 
$arr=array(1,3,5,7,9,11); 
//逆向排序的数组 
$arr2=array(11,9,7,5,3,1); 
//对正向排序的数组进行二分查找 
function searchpart($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);//这里只需要保证中间项下标的计算值为整数即可，也可以四舍五入，不影响结果 
if($arr[$mid]>$x){//如果中间项的值大于待查值，说明代差值位于中间项的左边，因此，起始下标不变，结束下标变成中间项下标减1，第一次搜索的是$arr[0]-$arr[5]的话，下一次搜索 
$end=$mid-1;//$arr[0]-$arr[1] 
}elseif($arr[$mid]<$x){//如果中间项的值小于待查值，说明代差值位于中间项的右边，因此，结束下标不变，起始下标变成中间项下标加1，第一次搜索的是$arr[0]-$arr[5]的话，下一//次搜索是，$arr[3]-$arr[5] 
$start=$mid+1; 
}else{//找到了，返回待查值下标 
return $mid; 
} 
} 
} 
//对逆向排序的数组进行二分查找 
function searchpart2($arr,$x){ 
$start=0; 
$end=count($arr)-1; 
while($start<=$end){ 
$mid=intval(($start+$end)/2);//这里只需要保证中间项下标的计算值为整数即可，也可以四舍五入，不影响结果 
if($arr[$mid]>$x){//如果中间项的值大于待查值，说明代差值位于中间项的右边，因此，结束下标不变，起始下标变成中间项下标加1，第一次搜索的是$arr[0]-$arr[5]的话，下一次搜索 
$start=$mid+1;//$arr[3]-$arr[5] 
}elseif($arr[$mid]<$x){//如果中间项的值小于待查值，说明代差值位于中间项的左边，因此，起始下标不变，结束下标变成中间项下标减1，第一次搜索的是$arr[0]-$arr[5]的话，下一//次搜索是，$arr[0]-$arr[1] 
$end=$mid-1; 
}else{//找到了，返回待查值下标 
return $mid; 
} 
} 
} 
echo searchpart2($arr,5).&#39;<br>&#39;; 
echo searchpart2($arr2,5); 
?>

PHP的二分查找演算法實現 
最近整理了下以前學習的演算法知識,雖然在WEB開發時演算法用到的情況比較少,但還是把一些有用的演算法做下備份。 
折半查找法也稱為二分查找法，它充分利用了元素間的次序關係，採用分治策略，可在最壞的情況下用O(log n)完成搜尋任務。 
【基本思想】 
將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止。如果xa[n/2]，則我們只要在陣列a的右半部繼續搜尋x。 
二分搜尋法的應用極為廣泛，而且它的思想易於理解。第一個二分搜尋演算法早在1946 年就出現了，但是第一個完全正確的二分搜尋演算法直到1962年才出現。 Bentley在他的著作《Writing Correct Programs》中寫道，90%的電腦專家不能在2小時內寫出完全正確的二分搜尋演算法。問題的關鍵在於準確地制定各次查找範圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的。 
PHP的二分查找演算法實作 

/** 
* 二分查找算法 
* 
* @param array $arr 有序数组 
* @param int $val 查找的数值 
* @return int 查找值存在返回数组下标,不存在返回-1 
*/ 
function binary_search($arr,$val) 
{ 
$l = count($arr);//获得有序数组长度 
$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);

更多 使用PHP實作二分查找演算法碼分享相關文章請關注PHP中文網！