/** * 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; } }
当前标题:数据结构之查找(php代码实现)
网站路径:https://www.cdcxhl.com/article6/gpcgig.html
成都网站建设公司_创新互联,为您提供电子商务、企业网站制作、响应式网站、建站公司、网站策划、品牌网站建设
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联