程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> PHP綜合 >> 使用PHP實現二分查找算法代碼分享

使用PHP實現二分查找算法代碼分享

編輯:PHP綜合

第一種方法:
【二分查找要求】:1.必須采用順序存儲結構 2.必須按關鍵字大小有序排列。   
【優缺點】折半查找法的優點是比較次數少,查找速度快,平均性能好;其缺點是要求待查表為有序表,且插入刪除困難。因此,折半查找方法適用於不經常變動而查找頻繁的有序列表。   
【算法思想】首先,將表中間位置記錄的關鍵字與查找關鍵字比較,如果兩者相等,則查找成功;否則利用中間位置記錄將表分成前、後兩個子表,如果中間位置記錄的關鍵字大於查找關鍵字,則進一步查找前一子表,否則進一步查找後一子表。
復制代碼 代碼如下:
<?php
//作者:遙遠的期待
//QQ:15624575
//主頁:http://www.phptogether.com/
//正向排序的數組
$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).'<br>';
echo searchpart2($arr2,5);
?>

PHP的二分查找算法實現
最近整理了下以前學習的算法知識,雖然在WEB開發時算法用到的情況比較少,但還是把一些有用的算法做下備份。
折半查找法也稱為二分查找法,它充分利用了元素間的次序關系,采用分治策略,可在最壞的情況下用O(log n)完成搜索任務。
【基本思想】
將n個元素分成個數大致相同的兩半,取a[n/2]與欲查找的x作比較,如果x=a[n/2]則找到x,算法終止。如果x<a[n/2],則我們只要在數組a的左半部繼續搜索x(這裡假設數組元素呈升序排列)。如果x>a[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);

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved