【数据结构】PHP实现查找表

【基本算法】

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

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

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

?>

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

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

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

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

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

以上输出: Process time: 0/s

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

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

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

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

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

【算法改进】

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

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!