斐波那契查找的前提是待查找的查找表必須順序存儲且有序。
相對于折半查找悠抹，一般將待比較的key值與第mid=（low+high）/2位置的元素比較统翩，比較結(jié)果分三種情況
1）相等,mid位置的元素即為所求
2）> ? ? ,low=mid+1;
3) ?< ? ? ,high=mid-1;
斐波那契查找與折半查找很相似，他是根據(jù)斐波那契序列的特點對有序表進行分割的渐溶。他要求開始表中記錄的個數(shù)為某個斐波那契數(shù)小1怜械，及n=F[k]-1;
開始將key值與第F[k-1]-1位置的記錄進行比較(即mid=low+F[k-1]-1),比較結(jié)果也分為三種
1）相等颅和，mid位置的元素即為所求
2）> ? ,low=mid+1,k-=2; (注意：此處是k=k-2)
說明:low=mid+1說明待查找的元素在[mid+1,hign]范圍內(nèi)，k-=2 說明范圍[mid+1,high]內(nèi)的元素個數(shù)為n-F[k-1]=F[k]-1-F[k-1]=F[k]-F[k-1]-1=F[k-2]-1個缕允，所以可以遞歸的應(yīng)用斐波那契查找
3)<? ? ,high=mid-1,k-=1;? (此處是k=k-1)
說明:low=mid+1說明待查找的元素在[low,mid-1]范圍內(nèi)融虽，k-=1 說明范圍[low,mid-1]內(nèi)的元素個數(shù)為F[k-1]-1
個，所以可以遞歸 的應(yīng)用斐波那契查找
代碼如下：
