数据结构之查找（php代码实现）
/*** Search_Seq($arr,$elem):顺序查找
* Search_Seq2($arr,$elem):顺序查找(优化)
* Search_bin($arr,$elem):二分查找
* SearchBST($elem):二叉搜索
*/
class Search{
public $arr;
function __construct($arr)
{
$this->arr = $arr;
}
/**
* 顺序查找
* @param $arr在$arr数组中查找
* @param $elem 查找数组中是否有存在元素$elem，有则返回在数组中的位置；没有则返回0
*/
public static function Search_Seq($arr,$elem){
for($i=0;$i<count($arr);$i++) {
if($arr[$i]==$elem){
return $i;
}
}
return 0;
}
//此算法是对上面算法的一种优化
public static function Search_Seq2($arr,$elem){
$i=0;
while($arr[$i]!=$elem){
$i++;
}
return $i;
}
/**
* 二分查找(也叫做折半查找),前提是数组必须有序——从小到大排列
* @param $arr在$arr数组中查找
* @param $elem 查找数组中是否有存在元素$elem，有则返回在数组中的位置；没有则返回0
*/
public static function Search_bin($arr,$elem){
$low=0;
$high=count($arr);
while($low<=$high){
$mid=round(($low+$high)/2);
// $mid=$low+($low+$high)*($elem-$arr[$low])/($arr[$high]-$arr[$low]); //若将$mid的值改为此句，则就成了插值查找了。这种查找算法在数据大小分布比较均匀的时候，效率会比折半查找高一些。
if($elem<$arr[$mid]){
$high=$mid-1;
}else if($elem>$arr[$mid]){
$low=$mid+1;
}else{
return $mid;
}
}
return 0;
}
/**
* 二叉排序树
* @param $elem
* @return int
*/
public function SearchBST($elem){
return $this->find($this->arr,$elem,0);
}
private function find($root,$elem,$i){
if($i>count($this->arr) || !$root){
return 'Error';
}
if($elem==$root){
return $i;
}
if($elem<$root && $i*2+1<count($this->arr)){
return$this->find($this->arr[$i*2+1],$elem,$i*2+1);
}else if($elem>$root && $i*2+2<count($this->arr)){
return$this->find($this->arr[$i*2+2],$elem,$i*2+2);
}
return 0;
}
}
页:
[1]