PHP查找算法

作者: 软件架构师笔记 | 来源:发表于2018-04-12 12:07 被阅读54次

    静态查找

    1. 顺序查找
    /**
    * Common search
    *
    * @param  array  $arr
    * @param  mixed  $item
    *
    * @return int
    */
    public function search(array $arr, $item)
    {
        for ($i = 0; $i < count($arr); $i++) {
            if ($arr[$i] == $item) {
                return $i;
            }
        }
    
        return -1;
    }
    
    1. 折半查找
    /**
    * Binary search
    *
    * @param  array  $arr
    * @param  mixed  $item
    *
    * @return int
    */
    public function binSearch(array $arr, $item)
    {
        if (empty($arr)) {
            return -1;
        }
    
        $low = 0;
        $high = count($arr) - 1;
    
        while ($low <= $high) {
            //$mid  = intval(($high + $low) / 2) 可能溢出
            $mid  = intval(($high - $low) / 2) + $low;
            $val = $arr[$mid];
    
            if($item == $arr) {
                return $mid;
            } elseif ($item < $val) {
                $high = $mid -1;
            } else {
                $low = $mid + 1;
            }
        }
    
        return -1;
    }
    
    1. 递归折半查找
    /**
    * Recursion search 
    *
    * @param  array $arr
    * @param  mixed $item
    * @param  int  $low
    * @param  int  $high
    *
    * @return int 
    */
    
    public function binRecSearch(array $arr, $item, $low, $high){
        if (empty($arr) || $low > $high || $low < 0) {
            return -1;
        }
    
        $low = 0;
        $high = count($arr) - 1;
    
        if ($low <= $high) {
            $mid = intval(($high - $low) / 2) + $low;
            if ($item == $arr[$mid]) {
                return $mid;
            } elseif ($item < $arr[$mid]) {
                return binRecSearch($arr, $item, $mid + 1, $high);
            } else {
                return binRecSearch($arr, $item, $low, $mid - 1);
            }
        }
    
        return -1;
    }
    

    相关文章

      网友评论

        本文标题:PHP查找算法

        本文链接:https://www.haomeiwen.com/subject/fpdxkftx.html