斐波那契数列查找算法

1. 黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位 数字的近似值是 0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神
   奇的数字，会带来意向不大的效果。
2. 斐波那契数列 {1,1,2,3,5,8,13,21,34,55} 发现斐波那契数列的两个相邻数 的比例，无限接近 黄金分割值 0.618
   8.5.2斐波那契(黄金分割法)原理: 斐波那契查找原理与前两种相似，仅仅改变了中间结点（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）+1 。该式说明： 只要顺序表的长度为 F[k]-1，则可以将该表分成长度为 F[k-1]-1 和 F[k-2]-1 的两段，即如上图所示。从而中间位置为 mid=low+F(k-1)-1
3. 类似的，每一子段也可以用相同的方式分割 3) 但顺序表长度 n 不一定刚好等于 F[k]-1，所以需要将原来的顺序表长度 n 增加至 F[k]-1。这里的 k 值只要能使 得 F[k]-1 恰好大于或等于 n 即可，由以下代码得到,顺序表长度增加后，新增的位置（从 n+1 到 F[k]-1 位置）， 都赋为 n 位置的值即可。 while(n>fib(k)-1) k++;

具体实现如下：

public class FibonacciSearch {
    //数组的长度
    public static int  maxSize=20;


    //得到一个斐波那契数列，非递归实现
    public static int [] fib()
    {
        int [] f=new int [maxSize];

        f[0]=1;
        f[1]=1;
        for (int i = 2; i <maxSize ; i++) {

            f[i]=f[i-1]+f[i-2];
        }

        return f;
    }
    //斐波那契数列查找算法，非递归实现
    public static int fibSearch(int [] arr,int key) {
        int low = 0;

        int high = arr.length - 1;

        int k = 0;  //斐波那契数列的分割值下标

        int mid = 0; //记录mid的值

        int f[] = fib(); //获取到斐波那契数列
        //获取斐波那契数列分割数组的下标
        while (high > f[k] - 1) {
            k++;

            //因为f[k]值可能大于a的长度，因此我们需要使用Arrays，指向temp[]
            //不足的部分会使用0填充
        }

        int[] temp = Arrays.copyOf(arr, f[k]);

        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        //使用while来循环处理，找到我们的数key
        while (low <= high) { //只要这个体条件满足，就可以找
            mid = low + f[k - 1] -1;

            if (key < temp[mid]) { //我们应该继续向数组前面查
                high = mid - 1;
                k--;
            } else if (key > temp[mid]) { //我们应该继续向数组后面查
                low = mid + 1;
                k -= 2;
            } else {//找到
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;

    }
}

public class FiboSearch3 {

	//斐波那契数列查找算法
	//前提：有序
	//还有几处，理解的还很不到位。
	//但根据记忆口诀，目前算法已经可以复写。但如果不理解，或许记忆不会深刻。
	//目前惟手勤尔，真的可行
	public static void main(String[] args) {
		int [] arr = { 1,8,10,89,1000,1234 };
		System.out.println( search(arr,1) );
	}
	//获得斐波那契数列
	public static int[] fibo( int length ) {
		int [] f = new int[length];
		//头两个元素固定
		f[0] =1;
		f[1] =1;
		for (int i = 2; i < f.length; i++) {
			//元素规律
			f[i] = f[i-1] + f[i-2];
		}
		return f;
	}
	
	public static int search( int [] arr, int findVal ) {
		int left = 0;
		int right = arr.length-1;
		int mid = 0;
		int k = 0;
		int [] f = fibo(10);
		
		//根据数列对照得到数组大小
		while( right > f[k] -1 ) {
			k++;
		}
		
		//根据新大小生成新数组
		int [] temp = Arrays.copyOf(arr, f[k]);
		
		//补充数据
		for (int i = right+1; i < temp.length; i++) {
			temp[i] = arr[right];
		}
		
		//当左索引比右索引小时，说明数组未遍历完
		//当判断条件为假时，说明数组遍历完毕
		while( left <= right ) {
			mid = left + f[k-1] -1;
			//判断当前寻找的值是否比中间值小
			if( findVal < temp[mid] ) {
				right = mid - 1;
				k--;
			}else if( findVal > temp[mid] ) {
				left = mid+1;
				k-=2;
			}else {
				if(mid <= right) {
					return mid;
				}else {
					return right;
				}
			}
		}
		//未找到搜索值，返回-1标记失败。
		return -1;
	}

}

斐波那契数列

  在数学中，斐波那契数列的定义是：
$$f_n=\{\begin{array}{lc}n& (n=0,1)\\ f_{n-1}+f_{n-2}& (n⩾2)\end{array}$$
  很明显，这是一个递归定义，很多数据结构书中也拿斐波那契数列来讲解递归的过程。根据这个定义可以得到一个斐波那契数列：

  先讨论一下这个数列值如何用程序来产生，这是个递归定义，那肯定是可以用递归函数来生成这个数列了。

unsigned __int64 Fib(int n)
{
	if (n <= 1)
		return n;
	else
		return Fib(n - 1) + Fib(n - 2);
}

  这几行代码非常简单，但是在实际过程中不可这么用。为什么？用这个函数生成长度为100的数列，跑一跑就知道了.

void main(void)
{
	printf("斐波那契数列：\r\n");
	for (int i = 0; i < 100; i++)
	{
		printf("%3d:%I64u \r\n", i,Fib(i));
	}
}

  这总共不超过20行的代码，用一台六年前的笔记本整整跑了一个半小时，只计算到数列的第五十一个值 ，虽然笔记本性能一般，但是这几行代码异常耗时是有内层机理的。用这个方法计算一个斐波那契数列，越到后面越耗时，时间的增加就跟数列值的增加一样，后一个值的计算用时是前两个值计算用时的总和。以数列第3、4、5个值为例：

  要计算 $Fib(5)$ 就要计算 $Fib(4)$ 和 $Fib(3)$，同样，要计算 $Fib(4)$ 就要计算 $Fib(3)$ 和 $Fib(2)$，一直到叶子节点，即 $Fib(1)$ 或 $Fib(0)$ 才一层层返回，也就是说 $Fib(5)$ 的计算重复了 $Fib(4)$ 和 $Fib(3)$ 的计算过程，做了大量的重复计算过程，而且这个增长接近2的指数级。

  像斐波那契数列这样的递归计算不适用于实际，那就要想办法将它转化成其他形式，例如迭代运算。

  通过$i$，$p$，$q=i+p$往后移就可以得到数列中任意想要的值。写成代码：

unsigned __int64 Fib(int n)
{
	unsigned __int64 i = 0, p = 1, q = 1;
	if (n <= 1) return n;
	else if (n == 2) return 1;
	else
	{
		for (int j = 2; j < n; j++)
		{
			i = p;
			p = q;
			q = i + p;
		}
		return q;
	}
}

  程序跑完才发现，64位无符号整型仍然不够，还是产生了溢出。
  去年研究生考试结束后在南京面试，笔试里就有一道斐波那契数列的程序题，一开始写的程序是动态申请一块内存作为数组，前两个值相加的和放到后一个单元里面，然后一直迭代下去，产生一组斐波那契数列。面试官就说如果数列很长呢，还能用动态申请的方式去生成这个数列吗？于是就写了迭代版本的Fib函数，面试官看了一会，好像还是没有get到他的要求。出了公司门一个瞬间有个念头：难道他想要我写出递归版本？他招的是嵌入式软件工程师啊。。亦或者是斐波那契数列的生成有更优的方法，但是本人愚钝。。。

斐波那契查找

  斐波那契查找又是怎么回事呢？

  从这颗斐波那契树中可以大致看出来，左子树和右子树的结点数虽然不等，但是左子树的结点数永远不会超过右子树结点数的两倍，可以大致的看成是相对均匀的两部分，如果将数据以这个树形建成一颗搜索树，那么每颗子树根节点的序号就可以看成二分搜索的$mid$。
  为什么要这么做？在对半查找中$mid=(low+high)/2$，这里$mid$的计算运用了除法，有些处理器中并没有浮点运算单元，像51单片机进行乘除运算就比较费资源。斐波那契查找正是极力想要避免查找过程中出现乘除运算，查找过程中$mid$的计算可以直接通过斐波那契数列得到，当表长为12($f_7-1$)时，$mid=8$，即$mid$值为数列的前一个值。
  既然斐波那契数列值是用来作为$mid$值，那么数列值应该是不重复的，否则会发生重复比较甚至出错，对于下列数列值中，1有重复，那么应该去掉一个，但是只去掉一个1，会导致整个数列不符合斐波那契公式，无法计算，所以去掉0和一个1，但是斐波那契的阶数保持不变。

  为了直观，建立一颗$1$~$12$的斐波那契树

  1，2，3，5，8这条路径上确实满足斐波那契数列，可每颗子树的右子树并不满足。但是是有规律的，每颗右子树结点的值减去双亲结点的值却是满足斐波那契数列的。
  为了简单，假设表长为12($f_7-1$)，为什么表长需要定义为$f_m-1$呢，这里跟二叉判定树是一样的，为了树形完整，便于运算分析。可以写出查找函数：

int search(s_list lst, int k, s_eletype* x)
{
	int i = 1, p = 1, q = 2, t, n = lst.size;
	while (q <= n)                       //见注释1
	{                                    
		i = p;
		p = q;
		q = i + p;
	}
	i = p;                               //见注释2
	p = q - i;
	q = i - p;

	for (;;)
	{
		if (k == lst.element[i-1].key)
		{
			*x = lst.element[i-1];
			return true;
		}
		else
		{
			if (k < lst.element[i-1].key)
			{
				if (q == 0) return false;
				else
				{
					i = i - q;
					t = p;
					p = q;
					q = t - q;
				}
			}
			else
			{
				if (p == 1)return false;
				else
				{
					i = i + q;
					p = p - q;
					q = q - p;
				}
			}
		}
	}
}

注释1：计算斐波那契数列的最后三个数值：$i=f_{m-2}$，$p=f_{m-1}$，$q=f_m$。
注释2：颠倒$i,p,q$，变成$i=f_{m-1}$，$p=f_{m-2}$，$q=f_{m-3}$。
$p,q$的大小永远往下减，代表的是以$i$为根节点的子树所在阶数的斐波那契数列最高两位数列值。

  因为斐波那契树不是一颗完全二叉树，所以将数据构建成的斐波那契数的高度会高于[lbn]+1，所以在最坏的情况下，斐波那契查找的时间性能不如对半查找；但是斐波那契的查找过程中没有乘除运算，所以在没有浮点运算单元的处理器中理论上平均性能会优于对半查找。
  之所以说是理论上要比对半查找性能好，那是因为我们可以将对半查找的乘除运算转换为移位运算呀，乘2运算转换为左移一位，除2运算转换为右移一位，那平均性能妥妥的比斐波那契查找好。

本篇完 😉