数据结构-二分查找,分别用递归与非递归实现

?先来看效果!

非递归查找
待查找数组: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);
	}
}
?>