数据结构-二分查找,分别用递归与非递归实现
?先来看效果!
非递归查找
待查找数组:Array ( [0] => 0 [1] => 1 [2] => 8 [3] => 12 [4] => 28 [5] => 33 [6] => 40 [7] => 49 )
查找33的结果:
33存在
递归查找
待查找数组:Array ( [0] => 0 [1] => 1 [2] => 8 [3] => 12 [4] => 28 [5] => 33 [6] => 40 [7] => 49 )
查找33的结果:
33存在
这里使用php实现,直接贴代码!
<?php
$ars = [1,12,0,40,33,8,49,28];
sort($ars);
//非递归二分查找
print("非递归查找<br/>待查找数组:");
print_r($ars);
echo "<br/><br/>";
print("查找33的结果:");
echo "<br/>";
$rd = Dichotomy($ars,1);
if($rd!=-1){
echo "33存在<hr/>";
}else{
echo "33不存在<hr/>";
}
//递归二分查找
print("递归查找<br/>待查找数组:");
print_r($ars);
echo "<br/><br/>";
print("查找33的结果:");
echo "<br/>";
$rd = RecursionDichotomy($ars,33,count($ars),0);
if($rd!=-1){
echo "33存在";
}else{
echo "33不存在";
}
//非递归二分查找
function Dichotomy($arr,$key){
$min = 0;
$max = count($arr)-1;
while($min<=$max){
$cen = ceil(($min+$max)/2);
if($key === $arr[$cen]){
return $cen;
}elseif($key > $arr[$cen]){
$min = $cen + 1;
}else{
$max = $cen - 1;
}
}
return -1;
}
//递归二分查找
function RecursionDichotomy($arr,$key,$max,$min){
if($min>$max){return -1;}
$cen = ceil(($min+$max)/2);
if($key === $arr[$cen]){
return $cen;
}elseif($key > $arr[$cen]){
return RecursionDichotomy($arr,$key,$max,($cen + 1));
}else{
return RecursionDichotomy($arr,$key,($cen - 1),$min);
}
}
?>
-
递归和非递归有什么不同?
快捷登陆