php 二分查找

php 二分查找

先说原理:

二分查找算法是在有序数组中用到的较为频繁的一种算法,在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间复杂度为O(n),但二分查找算法则更优,因为其查找时间复杂度为O(log2 n),比如数组{0,1,2,3,4,5,6,7,8 9},查找元素6,用二分查找的算法执行的话,其顺序为:

    1.第一步查找中间元素,即4,由于4<6,则6必然在4之后的数组元素中,那么就在{5,6,7,8,9}中查找,

    2.寻找{5,6,7,8,9}的中位数,为7,7>6,则6应该在7左边的数组元素中,那么只剩下{5,6},按此类推就可以找到了。

二分查找算法就是不断将数组进行对半分割,每次拿中间元素和goal进行比较。代码如下演示,也可以用递归算法实现,但是考虑到递归算法效率低,一般不建议采用

限制(效率高,但是也有硬伤!):

1必须是有序数列

2必须存在数组中

大概原理懂了,下变上实例代码:

$arr = array(
	1,2,3,4,6,7,8,9,10,11,12,13,14
);
var_dump(binSearch(6,$arr));

//二分查找
//假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;
//若x小于当前位置值,则在数列的前半段中查找;若x大于当前位置值则在数列的后半段中继续查找,直到找到为止
function binSearch($toSearch,$arr)
{
    //确定当前的检索范围
    $nCount = count($arr);
    //低位键,初始为0
    $nLowNum = 0;
    //高位键,初始为末尾 
    $nHighNum = $nCount - 1;

    while($nLowNum <= $nHighNum) {
        //选定大概中间键
        $nMiddleNum = intval(($nHighNum + $nLowNum)/2);

        if($arr[$nMiddleNum] > $toSearch) {
            //比检索值大
            $nHighNum = $nMiddleNum - 1;
        } elseif ($arr[$nMiddleNum] < $toSearch) {
            //比检索值小
            $nLowNum = $nMiddleNum + 1;
        } else {
            return $nMiddleNum;
        }
    }

    return false;
}

输出结果:

微信截图_20180913125546.png

你学会了吗?


php 二分查找

喜欢(1)

评论 抢沙发

表情