本文實例講述了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程序設計有所幫助。
