基于二分法 此算法依靠斐波那契数列 来跳转比较位置 在玩数位板所以有了手写图 单步骤原理如下
---C语言实现
#include<stdio.h> #include<stdlib.h> #define RETURN_FAIL -1 //斐波那契查找 int FibonacciSearch(int *Src_int,int Src_len,int SearchNum) { int LowIndex; int HighIndex; int MidIndex; int *phead = NULL; int count; int loop; int LastNum; int LastLastNum; int CurrentNum; if(Src_int == NULL || Src_len <= 0)return RETURN_FAIL; //创建斐波那契数列 LastNum = 1; LastLastNum = 1; CurrentNum = LastNum+LastLastNum; count = 3; while(Src_len >= CurrentNum) { LastLastNum = LastNum; LastNum = CurrentNum; CurrentNum = LastNum+LastLastNum; count++; } phead = (int *)malloc(sizeof(int)*(count)); LastNum = 1; LastLastNum = 1; phead[0] = 0; phead[1] = LastNum; phead[2] = LastLastNum; for(loop = 3;loop<=count;loop++) { phead[loop] = LastNum+LastLastNum; LastLastNum = LastNum; LastNum = phead[loop]; } //查找 LowIndex = 1; HighIndex = Src_len; while(LowIndex <= HighIndex) { MidIndex = LowIndex+phead[count-1]-1; if(MidIndex >= Src_len)MidIndex = Src_len-1; if(SearchNum == Src_int[MidIndex]) { return MidIndex; } else if(SearchNum > Src_int[MidIndex]) { LowIndex = MidIndex+1; count-= 2; } else { HighIndex = MidIndex-1; count-= 1; } } return RETURN_FAIL; } int main() { int result; int test[] = {0,1,8,16,23,35,47,59,78,88,99,123,234,555}; result = FibonacciSearch(test,sizeof(test)/sizeof(test[0]),555); printf("%d\n",result); system("pause"); return 0; }