【基本算法】

假设有一个数组，需要找出某个值在该数组中的位置。

<?
//二分查找
function@H_403_16@bin_sch(@H_403_16@$array,@H_403_16@$low,@H_403_16@$high,@H_403_16@$k){
if(@H_403_16@$low<=@H_403_16@$high){
@H_403_16@$mid=@H_403_16@intval((@H_403_16@$low+@H_403_16@$high)/@H_403_16@2);
if(@H_403_16@$array[@H_403_16@$mid]==@H_403_16@$k){
return@H_403_16@$mid;
}elseif(@H_403_16@$k<@H_403_16@$array[@H_403_16@$mid]){
return@H_403_16@bin_sch(@H_403_16@$array,@H_403_16@$mid-@H_403_16@1,@H_403_16@$k);
}else{
return@H_403_16@bin_sch(@H_403_16@$array,@H_403_16@$mid+@H_403_16@1,@H_403_16@$k);
}
}
return-@H_403_16@1;
}

//顺序查找
function@H_403_16@seq_sch(@H_403_16@$array,@H_403_16@$n,@H_403_16@$k){
@H_403_16@$array[@H_403_16@$n]=@H_403_16@$k;
for(@H_403_16@$i=@H_403_16@0;@H_403_16@$i<@H_403_16@$n;@H_403_16@$i++){
if(@H_403_16@$array[@H_403_16@$i]==@H_403_16@$k){
break;
}
}
if(@H_403_16@$i<@H_403_16@$n){
return@H_403_16@$i;
}else{
return-@H_403_16@1;
}
}

?>

测试代码：
array.txt 文件里面包含了一百万条类似 2,3,4,5 这样的数据，下面通过顺序查找和二分查找来确定速度。

@H_403_16@//二分查找
<?PHP
set_time_limit(@H_403_16@0);
@H_403_16@$array=array();
@H_403_16@$file=@H_403_16@file_get_contents("./array.txt");

@H_403_16@$array=@H_403_16@explode(",",@H_403_16@$file);
@H_403_16@sort(@H_403_16@$array);

@H_403_16@$st=@H_403_16@time();
@H_403_16@$k=@H_403_16@43;
@H_403_16@$n=@H_403_16@count(@H_403_16@$array);
@H_403_16@$r=@H_403_16@bin_sch(@H_403_16@$array,@H_403_16@0,@H_403_16@$n-@H_403_16@1,@H_403_16@$k);
@H_403_16@$et=@H_403_16@time();

@H_403_16@$t=@H_403_16@$et-@H_403_16@$st;
echo"Processtime:".@H_403_16@$t."/s";
?>

以上输出: Process time: 0/s

//顺序查找
@H_403_16@<?PHP
set_time_limit(@H_403_16@0);
@H_403_16@$array=array();
@H_403_16@$file=@H_403_16@file_get_contents("./array.txt");
@H_403_16@$array=@H_403_16@explode(",@H_403_16@$file);

@H_403_16@$st=@H_403_16@time();
@H_403_16@$k=@H_403_16@43;
@H_403_16@$n=@H_403_16@count(@H_403_16@$array);
@H_403_16@$r=@H_403_16@seq_sch(@H_403_16@$array,@H_403_16@$k);
@H_403_16@$et=@H_403_16@time();

@H_403_16@$t=@H_403_16@$et-@H_403_16@$st;
echo"Processtime:".@H_403_16@$t."/s";
?>

以上输出结果：Process time: 9/s

上面轻易就能够看出谁的效率高了。

【算法改进】

<?
//二分查找（递归消除）
function@H_403_16@bin_sch(@H_403_16@$array,@H_403_16@$k){
@H_403_16@$low=@H_403_16@0;
@H_403_16@$high=@H_403_16@$n-@H_403_16@1;
while(@H_403_16@$low<=@H_403_16@$high){
@H_403_16@$mid=@H_403_16@intval((@H_403_16@$high-@H_403_16@$low)/@H_403_16@2);
if(@H_403_16@$array[@H_403_16@$mid]==@H_403_16@$k)
return@H_403_16@$mid;
elseif(@H_403_16@$k<@H_403_16@$array[@H_403_16@$mid]){
@H_403_16@$high=@H_403_16@$mid-@H_403_16@1;
}else{
@H_403_16@$low=@H_403_16@$mid+@H_403_16@1;
}
}
return-@H_403_16@1;
}

//顺序查找（改进版）
function@H_403_16@seq_sch(@H_403_16@$array,@H_403_16@$k){
@H_403_16@$array[@H_403_16@$n]=@H_403_16@$k;
for(@H_403_16@$i=@H_403_16@0;;@H_403_16@$i++){
if(@H_403_16@$array[@H_403_16@$i]==@H_403_16@$k){
break;
}
}
if(@H_403_16@$i<@H_403_16@$n){
return@H_403_16@$i;
}else{
return-@H_403_16@1;
}
}
?>

能看出上面两个函数做了什么改变吗？效率提升了多少？