当前位置： 移动技术网 > IT编程>开发语言>PHP > 二分查找算法

二分查找算法

2018年03月10日  | 移动技术网IT编程  | 我要评论

艾怡良遭群轰,巴马斧头帮,全球通充值卡

二分查找算法的前提：

　　1，针对的是索引数组；

　　2，针对的是已经排好的数组。

代码演示：

//函数功能：从数组$arr中的位置$begin开始到位置$end之间找数据$s
function binary_search($arr,$s,$begin,$end)
{
    $mid = floor(($begin+$end)/2); // 定位中间的位置
    $mid_value = $arr[$mid];//取得中间项的值
    if($mid_value == $s)
    {
        return true;
    }else if($mid_value >$s)
    {
        if($begin > $mid-1)//如果开始位置都比结束位置大了，表示肯定找不到了
        {
            return false;
        }
        //中间项比要找的$s大，就去左边找吧：
        $re = binary_search($arr,$s,$begin,$mid-1);
    }else
    {
        if($mid+1 > $end)//如果开始位置比结束位置大了，表示肯定找不到了
        {
            return false;
        }
        //中间项比要找的$s小，就去右边找吧；
        $re = binary_search($arr,$s,$mid+1,$end);
    }
    return $re;
}

测试代码：

<?php
$a = array(1,3,11,18,19,22,25,33,34,38,44,55,56,58);
$search = 35;//要找的数
$len = count($a); // 数量，自然，最大下标是len-1

//使用binary_search()函数从$a中到len-1位置找$search
$v1 = binary_search($a,$search,0,$len-1);
echo "结果为：";
var_dump($v1);

测试结果：

·　　结果为：bool(false)

有关二分法查找算法的效率（性能）问题的一点说明：

　　1000个数据，约10次找出；

　　100完个数据，约20次找出；

　　10亿个数据，约30次找出；

　　40亿个数据，约32次找出。

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网