二分查找可以通过递归和循环来实现,
思路如下:
将要查找的数和中间数进行比较,
如果相等,则表示找到,返回下标
如果要查找的数小于中间这个数,则说明要查找的数分布在数组左边,修改right边界,使其等于middle-1,直接等于middle,如果查找不到,会造成死归,
如果要查找的数大于中间这个数,则说明要查找的数分布在数组的右边,修改left边界,使其等于middle+1,直接等于middle,如果查找不到,也会造成死归,
递归查找,使用一个静态变量保存下标,
没有查到,则返回-1
代码如下:
//递归二分查找 function binarySearchByRecursion($arr,$val,$left,$right){
static $index = -1; if($left>$right){
return $index;
}
$middle = floor(($left+$right)/2); if($val < $arr[$middle]){
//如果$middle不-1,则挑不出去,会一直递归下去
$right = $middle-1;
binarySearchByRecursion($arr,$val,$left,$right);
}elseif($val > $arr[$middle]){
$left = $middle+1;
binarySearchByRecursion($arr,$val,$left,$right);
}else{
$index = $middle;
}
return $index;
} //循环二分查找
//
function binarySearchByLoop($arr,$val){
$index = -1;
$left = 0;
$right = count($arr)-1; while($left <= $right ){ $middle = round(($left+$right)/2);
if($val < $arr[$middle]){
$right = $middle - 1;
}elseif($val > $arr[$middle]){
$left = $middle + 1;
}else{
$index = $middle;
break;
}
}
return $index;
}