PHP中实现二分法查找的两种方法

时间:2022-06-01 20:01:18

php实现二分法的查找其实很简单,跟我一起来看看怎么实现吧。

二分法查找需要数组是一个递增的数组。

想要写出二分法查找的代码,首先要懂得二分法实现查找的原理:

①要知道中间位置就需要知道起始位置和结束位置,然后取出中间位置的值来和我们的值做对比。

②如果中间值大于我们的给定值,说明我们的值在中间位置之前,此时需要再次二分,因为在中间之前,所以我们需要变的值是结束位置的值,此时结束位置的值应该是我们此时的中间位置。

③反之,如果中间值小于我们给定的值,那么说明给定值在中间位置之后,此时需要再次将后一部分的值进行二分,因为在中间值之后,所以我们需要改变的值是开始位置的值,此时开始位置的值应该是我们此时的中间位置,直到我们找到指定值。

④或者中间值等于最初的起始位置,或结束位置(此时说明给定值未找到)。

下面就看看怎么实现二分法吧!!!

/*
递归调用实现二分法查找
//$search 函数 $array为数组,$K为要找的值,$low为查找范围的最小键值,$high为查找范围的最大键值
//intval返回整数值*/
function search($array,$k,$low=0,$high=0){
//判断数组元素的数量
if(count($array)!=0 and $high==0){ //判断是否为第一次调用
//数组的元素个数
$high = count($array);
}
if($low <= $high){ //如果还存在剩余的数组元素
$mid = intval(($low+$high)/2); //取$low 与$high的中间值
//return $array[$mid];
if($array[$mid] == $k){
return $mid; //如果找到则返回
}elseif($k < $array[$mid]){
//如果上面没有找到,则继续查找
return search($array,$k,$low,$mid-1);
}else{
return search($array,$k,$mid+1,$high);
}
}
return "没有要查找的值";
}
$array = array(3,4,5,7,8,9,10);
echo search($array,4);




/*
//while循环实现二分法查找
*/
$arr = array(2,4,5,6,7,8,9,10);
$low = 0; //要查找范围的最小键值
$search = 6;
//计算出数组的长度
$high = count($arr)-1;
while($low <= $high){
//取得数组的中间键值
$mid = intval(($low+$high)/2);
if($arr[$mid]==$search){
//如果取出中间的下标值跟你要搜索的值相等的话,直接去除值得下标就行
echo "你要查找的值在数组内的下标为".$mid; break;
}elseif($arr[$mid] > $search){
$high = $mid -1;
}else{
$high = $mid+1;
}
}

是不是感觉很简单ㄟ(⊙ω⊙ㄟ)哈