#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define INT_MIN -9999

void createFibonacci(int[], int);     // 建立費氏數列
int findY(int[], int);          // 找Y值
int fibonacciSearch(int[], int, int);  // 費氏搜尋

int main(void) {
int number[] = {1, 2, 3, 5, 6, 8, 9, 10, 11};
int length = sizeof(number) / sizeof(int);
printf("數列：");
int i;
for(i = 0; i < length; i++)
printf("%d ", number[i]);
printf("\n輸入尋找對象：");
int find;
scanf("%d", &find);
if((i = fibonacciSearch(number, length, find)) >= 0)
printf("找到數字於索引 %d ", i);
else
printf("\n找不到指定數");
printf("\n");
return 0;
}
// 建立費氏數列
void createFibonacci(int Fib[], int length) {
Fib[0] = 0;
Fib[1] = 1;
int i;
for(i = 2; i < length; i++)
Fib[i] = Fib[i-1] + Fib[i-2];
}
// 找 y 值
int findY(int Fib[], int n) {
int i = 0;
while(Fib[i] <= n) i++;
i--;
return i;
}
// 費式搜尋
int fibonacciSearch(int number[], int length, int find) {
int* Fib = malloc(length * sizeof(int));
int f;
for(f = 0; f < length; f++) {
Fib[f] = INT_MIN;
}
createFibonacci(Fib, length);
int y  = findY(Fib, length + 1);
int m = length - Fib[y];
int x = y - 1;
// printf("\nx = %d, m = %d, Fib[x] = %d\n\n", x, m, Fib[x]);
    int i = x;
if(number[i] < find)
i += m;
int result = -1;
while(Fib[x] > 0) {
if(number[i] < find)
i += Fib[--x];
else if(number[i] > find)
i -= Fib[--x];
else {
result = i;
break;
}
}
free(Fib);
return result;
}