本文實例講述了PHP折半（二分）查找算法。分享給大家供大家參考，具體如下：
折半查詢只適用于已經按照正序或者逆序排序的數組，字符串等；
算法：
先取數組的中間位置，無中間位置，則向下取整；
從中間進行折半，大小判斷，進入前半段或者后半段；
再對前半段或者后半段進行同樣的折半查詢，
直到查詢到匹配的字符，才停止（本例用break，如果置于函數中，return即可）
php實現的代碼如下：
<?php$arr = array(1,2,3,4,5,6,7,8,9,10);//數組$key = 4;//要查詢的關鍵字$low = 0;//開始位的標志$high = count($arr);//終止位的標志while($low <= $high){//查詢開始結束的條件 $mid = floor(($low + $high)/2);//進行中間位置計算，向下取整 if($arr[$mid] == $key){//查詢成功 echo $arr[$mid]; break;//結束本頁執行，函數可用return }elseif($arr[$mid] > $key){ //查詢前半段，把結束標志移到中間位置前一位 $high = $mid - 1; }else{ //查詢后半段，把開始位置移到中間位置的后一位 $low = $mid + 1; }}/*運行結果：4*/?>補充：折半（二分）查找算法類：
/** * Description:php實現二分查找算法的類 * @author wzy */class binary_search{ public $arr; public $key; function __construct($arr,$key){ //這里初始化的數組已經是有序數組 $this->arr=$arr; $this->key=$key; } function binarysearch(){ $start=0; $end=count($this->arr)-1; while($start<=$end){ //mid的取值可以為上整數或者下整數 $mid=ceil(($start+$end)/2); //$mid=($start+$end)>>1; //$mid=intval(($start+$end)/2); if($this->arr[$mid]<$this->key){ $start=$mid+1; }else if($this->arr[$mid]>$this->key){ $end=$mid-1; }else{ return $mid; } } }}可能大家還會遇到這種情況，數組中的元素有重復數據，需要返回的是重復數據中的第一個元素的位置，例如
$arr=array(1,2,3,4,5,6,6,6,6,7,8);
查找6這個元素時返回的位置應該為5,而不是其他（下標從0開始計數），這樣需要在返回的mid進行判斷，代碼如下：
/** * Description:php實現二分查找算法的類 * @author wzy */class binary_search{ public $arr; public $key; function __construct($arr,$key){ //這里初始化的數組已經是有序數組 $this->arr=$arr; $this->key=$key; } function binarysearch(){ $start=0; $end=count($this->arr)-1; while($start<=$end){ //mid的取值可以為上整數或者下整數 $mid=ceil(($start+$end)/2); //$mid=($start+$end)>>1; //$mid=intval(($start+$end)/2); if($this->arr[$mid]<$this->key){ $start=$mid+1; }else if($this->arr[$mid]>$this->key){ $end=$mid-1; }else{ //返回第一個匹配的元素 for($i=$mid-1;$i>=0;$i--){ if($this->arr[$i]==$this->key){ $mid=$i; }else{ break; } } return $mid; } } }}希望本文所述對大家PHP程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
