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