斐波那契查找法 算法

1. 适用范围:

1. 比折半查找和插值查找更快
2. 数据顺序排列

2. 算法思想:

1. 属于折半查找的变种
   1. 按黄金分割比来划分区域
      1. 用斐波那契数列获得黄金分割比
         1. 不用0.618的原因: 构造斐波那契数列只用加法, 更快
         2. 具体划分方法:
            1. 分为两部分, 前面为较大的斐波那契数, 后面为较小的
               1. 两者相加正好等于较大的斐波那契数的下一个数

3. 在c语言中的实现

描述:

1. 构造斐波那契数列时要预留两个1,
   1. 让首尾阶段也能够一个一个查找, 即使没有黄金分割比
      1. 首位阶段就两种情况不能使用黄金分割比
         1. 即总长为2或1
2. 先把原始数据长度填充到最接近的斐波那契数
3. 分割区域只要用前一个斐波那契数来分前面部分即可
   1. 后面的自然就分出来了
4. 当斐波那契数列用完的时候, 就已经全部查找过了
5. 更新区域的时候要顺便把当前长度更新为新的斐波那契数 代码:

int fibonacciSearch(int data[],int length, int maxsize,int targetValue){
//length为data[]实际数据长度,maxsize为data[]最大长度
	int fiboIndex;
	/*构建斐波那契数列*/
	int *fiboArray=(int*)calloc(maxsize,sizeof(int));
	fiboArray[0]=1;//给Index=1的时候用,且为最后用到的索引
	fiboArray[1]=1;//给Index=2的时候用,且为最后用到的索引
	fiboArray[2]=1; fiboArray[3]=2;
	for(int i=4;fiboArray[i-1]<=maxsize;++i){
		fiboArray[i]=fiboArray[i-1]+fiboArray[i-2];
	}
	/*找到最接近的斐波那契数*/
	for(fiboIndex=0;fiboArray[fiboIndex]<length;++fiboIndex);
	/*填充数据到斐波那契数长度*/
	for(int i=length+1;i<=fiboArray[fiboIndex];++i){
		data[i]=data[length];
	}
	/*查找*/
	int left=1,mid;
	for(;fiboIndex>0;){
		mid=left-1 + fiboArray[fiboIndex-1];
		if(data[mid]==targetValue){
			free(fiboArray);
			/*辨别是否后面填充的数据*/
			if(mid>length)return length;
			return mid;
		}
		else if(data[mid]<targetValue){
			left = mid+1;
			fiboIndex-=2;//更新新区域的长度
		}
		else {
			fiboIndex-=1;//更新新区域的长度
		}
	}
	return 0;
	free(fiboArray);
}