斐波那契查找

斐波那契查找也是对有序表进行查找。与折半查找选择中间元素的方法不同，斐波那契查找是根据斐波那契序列对表进行分割。

斐波那契序列：0,1,12,3,5,8,13,21,............

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

具体请参考: http://blog.csdn.net/yunzhongguwu005/article/details/9341761

代码

#include<iostream>
using namespace std;
int searchfib(int n[], int value, int num) {
    //将生成的斐波那契数列存入数组
    int fib[20];
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 0; i < 20; i++) {
        fib[i + 2] = fib[i + 1] + fib[i];
    }
    //获取斐波那契数的下标
    int k = 0;
    while (num > fib[k] - 1) {
        k++;
    }
    //将原数组存入新数组，多出部分全部用原数组中最后一个元素存储
    int *temp,flag;
    flag= fib[k] - 1;
    temp = new int[flag];
    for (int i = 0; i < num; i++) {
        *(temp + i) = n[i];
    }
    for (int i = num; i < fib[k] - 1; i++) {
        *(temp + i) = n[num - 1];
    }
    int mid = 0;
    int low = 0;
    int high = num - 1;
    while (low <= high) {
        mid = low + fib[k - 1] - 1;
        if (temp[mid] < value) {
            low = mid + 1;
            k -= 2;
        }
        else if (temp[mid] > value) {
            high = mid - 1;
            k -= 1;
        }
        else {
            if (mid < num) {
                return mid + 1;
            }
            else {
                return num;
            }


        }
    }
    delete[]temp;
}
void main() {
    int num[12] = { 1,3,5,7,9,11,24,26,77,68,83,99 };
    int key = 1;
    int index=searchfib(num, key, 12);
    cout << key << "的位置是" << index << endl;
    system("pause");
}

---

本文总阅读量次 本站访客数人次