本文實(shí)例講述了PHP折半（二分）查找算法。分享給大家供大家參考，具體如下：
折半查詢只適用于已經(jīng)按照正序或者逆序排序的數(shù)組，字符串等；
算法：
先取數(shù)組的中間位置，無中間位置，則向下取整；
從中間進(jìn)行折半，大小判斷，進(jìn)入前半段或者后半段；
再對前半段或者后半段進(jìn)行同樣的折半查詢，
直到查詢到匹配的字符，才停止（本例用break，如果置于函數(shù)中，return即可）
php實(shí)現(xiàn)的代碼如下：
?php
$arr = array(1,2,3,4,5,6,7,8,9,10);//數(shù)組
$key = 4;//要查詢的關(guān)鍵字
$low = 0;//開始位的標(biāo)志
$high = count($arr);//終止位的標(biāo)志
while($low = $high){//查詢開始結(jié)束的條件
$mid = floor(($low + $high)/2);//進(jìn)行中間位置計(jì)算，向下取整
if($arr[$mid] == $key){//查詢成功
echo $arr[$mid];
break;//結(jié)束本頁執(zhí)行，函數(shù)可用return
}elseif($arr[$mid] > $key){ //查詢前半段，把結(jié)束標(biāo)志移到中間位置前一位
$high = $mid - 1;
}else{ //查詢后半段，把開始位置移到中間位置的后一位
$low = $mid + 1;
}
}
/*
運(yùn)行結(jié)果：4
*/
?>
補(bǔ)充：折半（二分）查找算法類：
/**
* Description:php實(shí)現(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ù)組中的元素有重復(fù)數(shù)據(jù)，需要返回的是重復(fù)數(shù)據(jù)中的第一個(gè)元素的位置，例如
$arr=array(1,2,3,4,5,6,6,6,6,7,8);
查找6這個(gè)元素時(shí)返回的位置應(yīng)該為5,而不是其他（下標(biāo)從0開始計(jì)數(shù)），這樣需要在返回的mid進(jìn)行判斷，代碼如下：
/**
* Description:php實(shí)現(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{
//返回第一個(gè)匹配的元素
for($i=$mid-1;$i>=0;$i--){
if($this->arr[$i]==$this->key){
$mid=$i;
}else{
break;
}
}
return $mid;
}
}
}
}
更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計(jì)算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運(yùn)算技巧總結(jié)》
希望本文所述對大家PHP程序設(shè)計(jì)有所幫助。
您可能感興趣的文章:- PHP實(shí)現(xiàn)的折半查找算法示例
- PHP 冒泡排序 二分查找 順序查找 二維數(shù)組排序算法函數(shù)的詳解
- php二分查找二種實(shí)現(xiàn)示例
- php順序查找和二分查找示例
- php數(shù)據(jù)結(jié)構(gòu)與算法(PHP描述) 查找與二分法查找
- 解析php二分法查找數(shù)組是否包含某一元素
- PHP二分查找算法示例【遞歸與非遞歸方法】
- PHP二分查找算法的實(shí)現(xiàn)方法示例
- PHP基于二分法實(shí)現(xiàn)數(shù)組查找功能示例【循環(huán)與遞歸算法】
- PHP實(shí)現(xiàn)的二分查找算法實(shí)例分析
