/**
 * 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$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+1arr)){
            return  $this->find($this->arr[$i*2+1],$elem,$i*2+1);
        }else if($elem>$root && $i*2+2arr)){
            return  $this->find($this->arr[$i*2+2],$elem,$i*2+2);
        }
        return 0;
    }
}