算法帝国
精通算法者,集数千宠爱于一生,睥睨程序,智慧人生......
二分查找数组中 n 所在的位置

关于一个排列好的数组需要找出,n 在数组所在的位置。如

$arr = array(1,2,3,3,3,3,4,4,5,6,7,8,9);

找出 4 在$arr 里的那个位置,可以看出是在$arr[6]。

思路: 二分法 

去数组中间的数middle,如果middle> n 那么往左(数组开始-middle)找否则往右找(middle-数组结尾),以此类推

时间复杂度:O(logn)

PHP代码如下:

<?php
global $begin;
$begin  = 0;

function minf($n,$arr){
	global $begin;
	// CO($arr,1);
	// CO('开始位置:'.$begin,1);
	if( count($arr) <=  1){ return 0;}
	$middle = intval( count($arr)/2 );
	$arr_left  = array_slice($arr,0,$middle);
	$arr_right = array_slice($arr,$middle,$len-1);
	// echo'分割点:'.$middle.'<br>';
	// echo  '分割点数据和$n:'.$arr[$middle],' - ',$n;
	if( $arr[$middle] > $n ){
		return minf($n,$arr_left);
	}elseif( $arr[$middle] < $n ){
		$begin += $middle;
		return minf($n,$arr_right);
	}elseif( $arr[$middle] == $n ){

		if( $arr[$middle - 1] == $n && $middle != 0 ){ return minf($n,$arr_left); }
		elseif( $arr[$middle + 1] == $n && $middle != $len ){ $begin += $middle; return minf($n,$arr_right); }
		else{ return $middle; }
	}
}
$arr = array(1,2,3,3,3,3,4,4,5,6,7,8,9);
echo '<br>'.($begin + minf(4,$arr));
?>
<< 上一篇 PHP 斐波那契数 d3js 矩阵图 下一篇 >>
文章标签
随意 | Created At 2014 By William Clinton | 蜀ICP备14002619号-4 |