数据结构之查找(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[0],$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; } }
本文出自 “一切皆有可能” 博客,请务必保留此出处http://noican.blog.51cto.com/4081966/1610884
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。