数据结构之查找（二）--斐波那契查找

    要了解斐波那契查找方法，必须先知道斐波那契数列和折半查找的思想。

一、斐波那契数列( F[] = {0, 1, 1, 2, 3, 5, 8, 13, 21,...... }; )

    大家在初中的时候都做过这题吧：如果兔子在出生两个月后就有繁殖能力，一对兔子每月能生出一对小兔子。假设所有兔子都不死，那么一年后可以繁殖多少对兔子呢？

    这题中：所经过的月数和兔子对数就构成了斐波那契数列。（读者自己下去算吧）

           

    由此可以得出斐波那契数列的表达式：

二、折半查找的思想

    折半查找就是每次迭代用中间值a[mid]来和我们要查找的值key比较大小，如果key<a[mid]则将末尾位置end指针指向mid位置，如果key>a[mid]则将起始位置start指针指向mid位置。终止条件是key=a[mid]或者start=end（表示没找到）。

三、斐波那契查找

    思想是：

        1、将所要被查找的数组a[]大小先扩充到斐波那契数列中最接近的数，扩充方法是用数组最后一个元素的值去填充扩充的位置。

        2、根据斐波那契数列规则：F[k] = F[k-1] + F[k-2]来分割要查找的数组a[]，取a[ start + F[k-1] - 1] 为中间位置指针。

注意：F[k]要减1的原因是数组是从0开始计算的

四、代码

//1.先建立斐波那契数列
//2.斐波那契查找

static int F[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144};


int fibonacci(int *a, int key, int length)
{
	int ret = 0;
	int k = 0;
	int start = 0;
	int mid;
	int end = length-1;
	
	while( end > F[k]-1 )  //开始长度对应的斐波那契
		k++;
			
//如果数组的长度达不到F[k]-1，那么用a[end]填充	
	int *b = (int *)malloc(F[k] * sizeof(int));

	memcpy(b,a,sizeof(int)*length);

		int i ;
		for(i = length;end < F[k]-1 && i<F[k];i++)
		{
			b[i] = a[length-1];
		}	

	while(start <= end && k>0)	
	{
		mid = start+F[k-1]-1;
		if( b[mid] > key )
		{
			end = mid-1;
			k--;
		}
			
		else if( b[mid] < key )
		{
			start = mid+1;
			k -= 2;
		}
				
		else
		{
			ret = 1;
			break;
		}
	}

	return ret;
}