与二分查找相比,斐波那契查找算法的明显优点在于它只涉及加法和减法运算,而不用除法。因为除法比加减法要占去更多的机时,因此,斐波那契查找的平均性能要比折半查找好。
参考文章:
http://blog.csdn.net/zpluw/article/details/7757331
下面给出源代码实现:
/*斐波那契查找法,前提是线性表必须有序,时间复杂度是O(logn)*/ #include<stdio.h> #define MAXSIZE 20 /*用非递归法构造一个斐波那契数组*/ void Fibonacci(int *f) { int i; f[0] = 0; f[1] = 1; for(i=2; i<MAXSIZE; i++) { f[i] = f[i-1] + f[i-2]; } } /*定义斐波那契查找法*/ int Fibonacci_Search(int *a, int n, int key) { int low, high, mid, i, k; int F[MAXSIZE]; Fibonacci(F); //构造一个斐波那契数组F low = 1; //最低下标记录为首位 high = n; //最高下标记录为末位 k = 0; while(n > F[k]-1) //计算n位于斐波那契数列的位置 { k++; } for(i=n; i<F[k]-1; i++) //将a的元素扩展到(某斐波那契数 - 1),即F[k]-1 { a[i] = a[n]; } while(low <= high) { mid = low + F[k-1] - 1; //计算当前分割的下标 if(key < a[mid]) { high = mid - 1; k -= 1; } else if(key > a[mid]) { low = mid + 1; k -= 2; } else { if(mid <= n) return mid; //若相等则说明mid即为查找到的位置 else return n; //若mid>n则说明是扩展的数值,返回n } } return -1; } int main() { int array[20] = {0,16,24,35,47,59,62,73,88,99};//注意数组的第一个元素0,能作为查找对象 int number = Fibonacci_Search(array, 9, 99); printf("位置是:array[%d]\n",number); return 0; }