斐波那契查找的前提是待查找的查找表必须顺序存储且有序。
相对于折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，比较结果分三种情况
1）相等,mid位置的元素即为所求
2）> ,low=mid+1;
3) < ,high=mid-1;
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F[k]-1;
开始将key值与第F[k-1]-1位置的记录进行比较(即mid=low+F[k-1]-1),比较结果也分为三种
1）相等，mid位置的元素即为所求
2）> ,low=mid+1,k-=2; (注意：此处是k=k-2)
说明:low=mid+1说明待查找的元素在[mid+1,hign]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-F[k-1]=F[k]-1-F[k-1]=F[k]-F[k-1]-1=F[k-2]-1个，所以可以递归的应用斐波那契查找
3)< ,high=mid-1,k-=1; (此处是k=k-1)
说明:low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F[k-1]-1
个，所以可以递归 的应用斐波那契查找
代码如下：
