Home > php教程 > php手册 > PHP实现查找表

PHP实现查找表

WBOY
Release: 2016-06-21 09:06:54
Original
1189 people have browsed it

【基本算法】

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


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

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

?>

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


//二分查找
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 "Process time: ". $t ."/s";
?>

以上输出: Process time: 0/s

//顺序查找
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, $n, $k); 
$et = time();

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

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


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


【算法改进】


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

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


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

 



Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Recommendations
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template