二分法应用之快速查找

作者: jaclon 分类: PHP 发布时间: 2011-05-20 12:58 ė 6没有评论

二分法的php应用,二分法查找可以理解为在数组的一半查找,如果没有在这一半的一半中查找,以此类推直到找到;相比普通的循环查找效率要快很多。

 
/**
 * 二分法查找
 * 
 * @param array $a    数组
 * @param mixed $val 要查找的数据
 * @return int            数据索引
 */
function binarySearch($a, $val){
	$low = 0;
	$high= count($a) - 1;
	while($low <= $high){
                $mid = intval(($low+$high)/2);
                if($a[$mid] == $val) return $mid;
                if($a[$mid] > $val){
			$high = $mid - 1;
		}else{
			$low = $mid + 1;
		}
	}
	return -1;
}

$a = array(4,5,6,7,8,9);
echo binarySearch($a,6); //结果为2

本文出自 肥蕉博客@IT技术,热门话题,生活随笔,美图欣赏,转载时请注明出处及相应链接。

本文永久链接: http://www.bananawolf.com/html/2011/05/525.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

Ɣ回顶部