PHP有序表查找----斐波那契查找

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了PHP有序表查找----斐波那契查找，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1581字，纯文字阅读大概需要3分钟。

内容图文

在前面我们介绍了二分查找、插值查找。其中的插值查找是对二分查找的改进。同样，本篇博客的主角—-斐波那契查找，也是对二分查找的改进（利用黄金分割原理）。

由于这个过程分析较之前的复杂，大家可以百度。

代码：

<?php
//斐波那契查找 利用黄金分割原理
//算法核心：
//1、当$num==$arr[$mid],查找成功
//2、当$num < $arr[$mid],新范围是第$low个到$mid-1个，此时范围个数为Fbi($k-1)-1个
//2、当$num > $arr[$mid],新范围是第$mid+1个到$high个，此时范围个数为Fbi($k-2)-1个
$i = 0;    //存储对比的次数
//为了实现该算法，我们首先要准备一个斐波那契数列
//@func 产生斐波那契数列
//@param 数列长度
function Fbi($i){
    if($i < 2){
        return ($i == 0 ? 0 : 1);
    }
    return Fbi($i - 1) + Fbi($i - 2);
}
//@param 待查找数组
//@param 待搜索的数字
function fbisearch(array $arr,$num){
    $count = count($arr);
    $lower = 0;
    $high = $count - 1;
    $k = 0;
    global $i;
    //计算$count位于斐波那契数列的位置
    while($count > (Fbi($k) - 1)){
        $k ++;
    }
    //将不满的数值补全，补的数值为数组的最后一位
    for($j = $count;$j < Fbi($k) - 1;$j ++){
        $arr[$j] = $arr[$count - 1];
    }
    //查找开始
    while($lower <= $high){
        $i ++;
        //计算当前分隔的下标
        $mid = $lower + Fbi($k - 1) - 1;
        if($num < $arr[$mid]){
            $high = $mid - 1;
            $k = $k - 1;    //斐波那契数列数列下标减一位 
        }else if($num > $arr[$mid]){
            $lower = $mid + 1;
            $k = $k - 2;    //斐波那契数列数列下标减两位
        }else{
            if($mid <= $count - 1){
                return $mid;
            }else{
                return $count - 1;	//这里$mid大于$count-1说明是补全数值，返回$count-1
            }
        }
    }
    return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = fbisearch($arr,62);
echo $pos."<br>";
echo $i;

以上就是PHP有序表查找----斐波那契查找的内容，更多相关内容请关注PHP中文网（www.gxlcms.com）！

内容总结

以上是互联网集市为您收集整理的PHP有序表查找----斐波那契查找全部内容，希望文章能够帮你解决PHP有序表查找----斐波那契查找所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端