php二分法-PHP源码

php二分法-PHP源码

[PHP]代码

$array = array(1,2,3,4,11,12,124,1245);
function found($array,$low,$hight,$k)
{
	$index = intval(($low+$hight) / 2);
	if($k == $array[$index])
	{
		return $index;
	}elseif($k < $array[$index])
	{
		return found($array,$low,$index-1,$k);
	}else{
		return found($array,$index+1,$hight,$k);
	}

}
echo found($array,0,$count,1245);

/**改进型不使用递归*/
function find($arr,$v)
{
	$start = 0;
	$end   = count($arr) - 1;

	while($start <= $end)
	{
		$index = intval(($start + $end) / 2);
		
		if($v < $arr[$index])
		{
			$end = $index - 1;
		}
		elseif($v > $arr[$index])
		{
			$start = $index + 1;
		}
		else
		{
			return $index;
		}
	}
	return -1;
}