斐波那契查找（黄金分割）

在插值查找的基础上，可以把比例值固定为0.618（黄金分割值），每次查找的时候都按照（mid前元素个数）/（mid后元素个数）=0.618来判断下一次查找的位置。为了满足初始状态下，数组元素个数符合斐波那契数列中的某个值，需要在查找之前填充数组。

C代码：

#include <stdio.h>#define MAXSIZE 20void fibonacci(int *f)
{
    int i;f[0] = 1;f[1] = 1;for(i=2; i < MAXSIZE; ++i){
    f[i] = f[i-2] + f[i-1];}
}int fibonacci_search(int *a,int key,int n)
{
    int low = 0;int high = n - 1;int mid = 0;int k = 0;int F[MAXSIZE];int i;fibonacci(F);while( n > F[k]-1 ) //F[k]可理解为元素个数{
    ++k;}for( i=n; i < F[k]-1; ++i){
    a[i] = a[high];}while( low <= high ){
    mid = low + F[k-1] - 1;if( a[mid] > key ){
    high = mid - 1;k = k - 1;}else if( a[mid] < key ){
    low = mid + 1;k = k - 2;}else{
    if( mid <= high ) {
    return mid;}else{
    return high;}}}return -1;
}int main()
{
    int a[MAXSIZE] = {
    1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88};int key;int pos;printf("请输入要查找的数字:");scanf("%d", &key);pos = fibonacci_search(a, key, 13);if( pos != -1 ){
    printf("\n查找成功！ 关键字 %d 所在的位置是: %d\n\n", key, pos);}else{
    printf("\n未在数组中找到元素:%d\n\n", key);}return 0;
}