查找算法

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

        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));

本文为崔凯原创文章,转载无需和我联系,但请注明来自冷暖自知一抹茶ckhttp://www.cksite.cn

• 上一篇： git常用命令
• 下一篇： 使用endroid/qrcode生成二维码