二分查找又稱折半查找，二分查找演算法要求資料必須是有順序的，以下是php實作二分查找演算法的程式碼。
一：遞歸方式
$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];
$target = 73;
$low = 0;
$high = count($array)-1;
function bin_search($array, $low, $high, $target){
if ( $low <= $high){
var_dump($low, $high);echo "\n";
$mid = intval(($low+$high)/2 );
if ($array[$mid] == $target){
return true;
}elseif ( $target < $array[$mid]){
return bin_search($array, $low, $mid-1, $target);
}else{
return bin_search($array, $mid+ 1, $high, $target);
}
}
return false;
}
$find = bin_search($array, $low, $high, $target);
var_dump($find);執行結果
int(0) int(25) int(13) int(25) int(20) int(25) int(20) int(21) bool(true)
我們看到，經過4次二分查找，查找區間不斷折半，最後找到了$target。
二：循環方式
$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];
$target = 73;
function bin_search($array, $target)
{
$low = 0;
$high = count($array)-1;
$find = false;
while (true){
if ($low <= $high){
var_dump($low, $high);echo "\n";
$mid = intval(($low + $high)/2);
if ($array[$mid] == $target){
$find = true;
break;
} elseif ($array[$mid] < $target){
$low = $mid+1;
} elseif ($array[$mid] > $target){
$high = $mid-1;
}
} else {
break;
}
}
return $find;
}
$find = bin_search($array, $target);
var_dump($find);執行結果
int(0) int(25) int(13) int(25) int(20) int(25) int(20) int(21) bool(true)
我們看到，兩種方式過程和結果相同。下面我們來測試下針對關聯數組的二分查找演算法：
$array = ['a'=>1,'b'=>3,'c'=>6,'d'=>9,'e'=>13,'f'=>18,'g'=>19,'h'=>29,'i'=>38];
$target = 19;
function bin_search($array, $target)
{
$low = 0;
$high = count($array)-1;
$key_map = array_keys($array);
$find = false;
while (true){
if ($low <= $high){
var_dump($low, $high);echo "\n";
$mid = intval(($low + $high)/2);
if ($array[$key_map[$mid]] == $target){
$find = true;
break;
} elseif ($array[$key_map[$mid]] < $target){
$low = $mid+1;
} elseif ($array[$key_map[$mid]] > $target){
$high = $mid-1;
}
} else {
break;
}
}
return $find;
}
$find = bin_search($array, $target);
var_dump($find);
执行结果
int(0)
int(8)
int(5)
int(8)
bool(true)兩次二分查找，找到了$target，針對關聯數組，我們使用了php的array_keys函數來獲得這個關聯有序數組的key，透過key間接比對$target和$array的值。
以上是PHP實作二分查找演算法（程式碼詳解）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
