您现在的位置是:首页 > 程序 > php网站首页php

php二分查找、顺序查找算法

  • 袁志蒙
  • 2018-07-15 20:18:29
  • 617 次阅读
php查找数组元素有内置的函数array_search和in_array,顺序查找对数组排序没有要求,二分查找法要求数组必须是一个有序数组!1.顺序查找function sequence_search...

php查找数组元素有内置的函数array_search和in_array,顺序查找对数组排序没有要求,二分查找法要求数组必须是一个有序数组!

1.顺序查找

function sequence_search($arr, $k){
	foreach($arr as $key=>$val){
		if($val==$k){
			return $key;
		}
	}
	return -1;
}

2.二分查找

思路分析:找到数组中间数,然后与要查找的数比较,如果要查找的数大于中间数,则说明要向后查找,否则向前查找,如果相等则说明已找到。

function binary_search($arr,$val,$left,$right){
	if($left > $right){
		return -1;
	}
	$middle = round(($left+$right)/2);
	if($arr[$middle]>$val){
		return binary_search($arr, $val, $left, $middle-1);
	}elseif($arr[$middle]<$val){
		return binary_search($arr, $val, $middle+1, $right);
	}else{
		return $middle;
	}
	
}

//定义被查找的数组(有序数组)
$arr = array(-3,-1,0,1,3,5,7);

//要查找的值
$val = 5;

echo  binary_search($arr, $val, 0, count($arr)-1);


TAG: 无标签

文章评论 (0)

    • 这篇文章还没有收到评论,赶紧来抢沙发吧~


Top