查找算法

        使用PHP描述顺序查找和二分查找(也叫做折半查找)算法,顺序查找必须考虑效率,对象可以是一个有序数组。

        冷暖自知一抹茶ck

        1. 顺序查找算法

//顺序查找(数组里查找某个元素) 
    function seq_sch($array, $n, $k){ 
        $array[$n] = $k; 
        for($i=0; $i<$n; $i++){ 
            if($array[$i]==$k){ 
                break; 
            } 
        } 
        if ($i<$n){ 
            return $i; 
        }
        else{ 
            return -1; 
        } 
    } 

===========================================
//顺序查找
    $arr = array( 1,3,6,8,23,69,100);
    var_dump(check_order($arr, 5));
    function check_order($arr, $num){
        //全部匹配
        $len = count($arr);
        for ($i=0; $i < $len; $i++) { 
            //判断
            if($arr[$i] == $num){
                return $i;
            }
        }

        return false;
    }

        2 . 二分查找算法

        2.1二分查找的定义:

        二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

        2.2算法的要求:

        从上面的定义我们可以知道,满足该算法的要求必须如下两点:

  •                 必须采用顺序存储结构。

  •                 必须按关键字大小有序排列。

        2.3算法的步骤

        其实,二分查找也还是比较容易理解的,大概就是一分为二,然后两边比较,保留有效区间,继续一分为二查找,直到找到或者超出区间则结束,所以二分查找的基本步骤是:

  1.         确定要查找的区间

  2.         确定要二分时的参照点

  3.         区间内选取二分点

  4.         根据二分点的值,综合左右区间情况以及求解的目的,舍去一半无用的区间

  5.         继续在有效区间重复上面的步骤


        这里,我主要采用递归和非递归两种方法实现,具体如下:

//二分查找-递归(数组里查找某个元素)
function bin_sch($array, $low, $high, $k){ 
    if ($low <= $high){ 
        $mid = intval(($low+$high)/2); 
        if ($array[$mid] == $k){ 
            return $mid; 
        }
        elseif ($k < $array[$mid]){ 
            return bin_sch($array, $low, $mid-1, $k); 
        }
        else{ 
            return bin_sch($array, $mid+1, $high, $k); 
        } 
    } 
    return -1; 
} 


=======================================

//二分查找-非递归
function check_break($arr,$res){
    //1. 得到数组边界
    $right     = count($arr);
    $left      = 0;
    //2. 循环匹配
    while ($left <= $right) {
        //3. 得到中间位置
        $middle = floor(($right + $left) /2 );
        //4. 匹配数据
        if($arr[$middle] == $res){
            return $middle+1;
        }
        //5. 没有找到
        if($arr[$middle] < $res){
            //值在右边
            $left = $middle + 1;
        }else{
            //值在左边
            $right = $middle - 1;
        }        
    }
    return false;
}
$arr     = array( 1,3,6,8,23,69,100);
var_dump(check_break($arr, 100));






冷暖自知一抹茶ck
请先登录后发表评论
  • 最新评论
  • 总共0条评论