前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >斐波那契查找

斐波那契查找

作者头像
JusterZhu
发布2022-12-07 20:26:35
3710
发布2022-12-07 20:26:35
举报
文章被收录于专栏:JusterZhuJusterZhu

概要

斐波那契又称黄金分割法。

  • 黄金分割点是指把一条线段分割为两部分,使其中一部分与全场之比等于另一部分之比。取其前三位数字的近似值是0.618.由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比。
  • 斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例,无限接近黄金分割值0.618。

斐波那契查找原理与前两种相似,仅仅改变了中间节点(mid)的位置,mid不再是中间或插值得到,二十位于黄金分割点附近,即mid = low + F(k - 1) -1; (F 代表斐波那契数列)如下图所示。

对F(k-1)-1的理解:

(1)由斐波那契数列F[k] = F[k-1] + F[k-2]的性质,可以得到(F[k]-1) = (F[k-1]-1) + (F[k-2]-1)。该式子说明,只要顺序表的长度为F[k-1],则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段,即如上图所示。从而中间位置为mid=low+F(k-1)-1。

(2)类似的,每一子段也可以用相同的方式分割。

(3)单顺序表长度n不一定刚好等于F[k-1],所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k-1]位置),都赋为n位置的值即可。

代码语言:javascript
复制
while(n>fib(k)-1)
   k++;

案例

对一个有序数组进行斐波那契查找{1,8,10,89,1000,1234},输入一个数看看数组是否存在次数,并且求出下标,如果没有就提示“没有这个数”。

代码语言:javascript
复制
public class FibonacciSearch
    {
        public static int MaxSize = 20;

        //因为后面我们mid=low + F(k-1)-1, 需要使用到斐波那契数列,因此我们需要先获取到一个斐波那契数列
        //非递归方式得到一个斐波那契数列

        public static int[] Fib() 
        {
            int[] fibArray = new int[MaxSize];
            fibArray[0] = 1;
            fibArray[1] = 1;
            for (int i = 2; i < MaxSize; i++)
            {
                fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
            }
            return fibArray;
        }

        /// <summary>
        /// 斐波那契查找算法
        /// </summary>
        /// <param name="array">数组</param>
        /// <param name="key">我们需要查找的关键码值</param>
        /// <returns>下标,没找到为-1</returns>
        public static int Search(int[] array, int key) 
        {
            int low = 0;
            int high = array.Length - 1;
            int k = 0; // 表示斐波那契分割数值的下标
            int mid = 0;//存放mid值
            int[] fibArray = Fib();//获取到斐波那契数列
            //获取到斐波那契分割数值的下标
            while (high > fibArray[k] - 1)
            {
                k++;
            }
            //因为f[k]可能大于数组array的长度,因此我们需要构造一个新的数组,并指向temp[]
            //不足的部分用0代替
            int[] temp = new int[fibArray[k]];
            Array.Copy(array, temp, array.Length);
            //实际上需求使用a数组最后的数填充temp
            for (int i = high + 1; i < temp.Length; i++ )
            {
                temp[i] = array[high];
            }
            //使用while循环来处理,找到我们的key
            while (low <= high)
            {
                //只要这个条件满足,就可以找
                mid = low + fibArray[k - 1] - 1;
                if (key < temp[mid])
                {
                    //说明我们应该继续向数组的前面查找(左边)
                    high = mid - 1;
                    //为什么是k--
                    //1.全部元素 = 前面的元素 + 后面的元素
                    //2.fibarray[k] = fibarray[k - 1] + fibarray[k -2];
                    //因为前面有fibarray[k-1]元素,所以可以继续拆分fibarray[k-1] = fibarray[k-2]+fibarray[k-3];
                    //即在fibarray[k-1]的前面继续查找k--
                    //即下次循环mid = fibarray[k-1-1]-1 
                    k--;
                }
                else if(key > temp[mid])
                {
                    //我们应该继续向数组的后面查找(右边)
                    low = mid + 1;
                    //为什么是k -=2
                    //说明
                    //1.全部元素 = 前面的元素 + 后面的元素
                    //因为后面有fibarray[k-2]元素,所以可以继续拆分fibarray[k-1] = fibarray[k-3]+fibarray[k-4];
                    //即在fibarray[k-2]的前面继续查找k-=2
                    //即下次循环mid = fibarray[k-1-2]-1 
                    k -= 2;
                }
                else
                {
                    //找到了,需要确定返回的是哪个下标
                    if (mid <= high)
                    {
                        return mid;
                    }
                    else
                    {
                        return high;
                    }
                }
            }
            return -1;
        }
    }
代码语言:javascript
复制
        static void Main(string[] args)
        {
            //初始化一个有序的100长度的数组
            int[] arr = { 1,8,10,89,1000,1234 };
            Console.WriteLine(FibonacciSearch.Search(arr,89));
            Console.Read();
        }
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-05-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 JusterZhu 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 概要
    • 案例
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档