Fibonacci search is an efficient search algorithm based on divide and conquer principle that can find an element in the given sorted array with the help of Fibonacci series in O(log N) time complexity. This is based on Fibonacci series which is an infinite sequence of numbers denoting a pattern which is captured by the following equation:F(n+1)=F(n)+F(n-1).
前言
斐波那契搜索(Fibonacci search) ,又称斐波那契查找,是区间中单峰函数的搜索技术。斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n],将原查找表扩展为长度为Fn,完成后进行斐波那契分割,即F[n]个元素分割为前半部分F[n-1]个元素,后半部分F[n-2]个元素,找出要查找的元素在那一部分并递归,直到找到。
斐波那契搜索
斐波那契搜索基本思想:
斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1,及n=F(k)-1;开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种:
(1)相等,则mid位置的元素即为所求;
(2)>,则low=mid+1,k-=2;
说明:low=mid+1说明待查找的元素在[mid+1,high]范围内,k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))=Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个,所以可以递归的应用斐波那契查找。
(3))<,则high=mid-1,k-=1。
说明:low=mid+1说明待查找的元素在[low,mid-1]范围内,k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个,所以可以递归的应用斐波那契查找。
在最坏情况下,斐波那契查找的时间复杂度还是O(log2n),且其期望复杂度也为O(log2n),但是与折半查找相比,斐波那契查找的优点是它只涉及加法和减法运算,而不用除法,而除法比加减法要占用更多的时间,因此,斐波那契查找的运行时间理论上比折半查找小,但是还是得视具体情况而定。
斐波那契搜索解析:
斐波那契搜索代码:
1 | import java.util.Arrays; |
延伸
斐波那契查找
斐波那契搜索
斐波那契查找原理解析
韩顺平数据结构和算法
Fibonacci Search - GeeksforGeeks