367   PHP

二分法比较常见的算法,来看看PHP如何实现

// 随机数组,用于查询
$arr = [];
for($i=0;$i<=20;$i=$i+rand(1,3)){ 
    array_push($arr,$i); 
} var_dump($arr); 

// 二分法查询函数 
// $arr数组,$val需要查询的值,$start开始位置,$end结束位置 
function getNum($arr,$val,$start,$end){ 
       // 查询完毕,防止值不存在时,造成死循环 
       if($start>$end){
		return null;
	}
	// 取中间的键名,以及获取键值
	$key=(int)(($start+$end)/2);
	$_val=$arr[$key];
	echo 'start:'.$start.',end:'.$end.',val:'.$val.',key:'.$key.',_val:'.$_val,"\n";
	if($val>$_val){
                // 循环查询
		return getNum($arr,$val,$key+1,$end);
	}else if($val<$_val){
		return getNum($arr,$val,$start,$key-1);		
	}else{
		return $key;
	}
	
}
// 获取查询值的key值
$key = getNum($arr,10,0,count($arr)-1);
var_dump($key);



Leave a Reply

Your email address will not be published. Required fields are marked *