【和我一起学算法】查找篇——斐波那契查找

作者：IT小白 | 2024-07-19 16:34:38

踩

斐波那契查找

三、斐波那契查找算法原理

斐波那契数列(Fibonacci)又称黄金分别数列,指的是这样一个数列:1,1,2,3,5,8,13,21,...。在数学上,斐波那契被递归方法如下定义：F(1)=1,F(2)=1,F(n)=F(n-1)+F(n-2)(n≥2)。该数列越往后,相邻的两个数的比值越趋向于黄金比例值(0.618),斐波那契查找就是在分法查找的基础上根据斐波那契数列进行分割的。

三、斐波那契查找
算法原理

Fibonacci查找与二分法查找几乎一样，只是在选取比较点(参照点)的位置有所区别。二分法选的是将数列中间的那个元素作为比较点(参照点)，而 Fibonacci查找则选取了数列中中间略微靠后点的位置作为比较点,也就是黄金分割点。假设被查找数列的长度为1，那么Fibonacci查找选取的比较点则在0.618的位置，这是由 Fibonacci数列的特性决定的。

Fibonacci查找作为二分法查找的变种,当被查找数列长度为20时，二分法首次查找选择的是数列中第10个元素做参照物，Fibonacci首次查找按照选取的是数列中第13个元素做参照物。如果被查找数列长度为100，二分法首次查找选择的是数列中第50个元素做参照物，而 Fibonacci首次查找则选取的是数列中第89个元素做参照物。数列越长,选择参照点的位置差别就越大。

既然叫作 Fibonacci查找，首先列出一个 Fibonacci数列[1,2,3,5,8,13,21]，这个 Fibonacci数列只是提供了被查找数列中参数点的位置，基本上就是下标。以 iList=[0.1,2,3,4,5,6,7,8,9]为例,共有len( iList)=10个元素。选择一个比len(iList)稍大的 Fibonacci数，也就是13。比13小一号的Fibonacci数就是8，那么首次选取的参照点就是iList中的iList[8]。如果被寻找数key比 iList[8]小，就看一下比8小一号的 Fibonacci数(5)，第二次选取的参照点就是 List[5]。以此类推,就是把 Fibonacci数当作被查找数列的位置参数来使用。

举例

以iList为被查找数列、key=7为例开始查找。

第一次查找

iList长度为10，Fibonacci数列中没有10，因此假设 iList的长度为13(13是 Fibonacci数)。比13小的 Fibonacci数是8，按照 Fibonacci查找的原理，实际上参照点应该是iList的第8个数字，iList也就[7]。为了直观,这里选取的是 iList[8]，这样也是可以的，如下图所示：

因为key比参照点iList[8]小，说明被查找数在iList的前面部分。

第二次查找

第二次查找是在iList[0:8]之间查找，这次被查找数列的长度是8，比8小一号的Fibonacci数是5，那么这次的参照点就是iList[5]，如下图所示：

此时key要比iList[5]大，说明被寻找的数在iList[0:8]的后半部分。也就是在iList[6:8]之间。

第三次查找

按照正常流程剩下有嫌疑的数只剩下iList[6]和iList[7]了，已经无需再用Fibonacci查找了，但我们这次查找还是使用Fibonacci的查找方式再来查找一次。

iList[6,8]之间只有两个数了，但是Fibonacci查找时确是在iList[6]、iList[7]、iList[8]这三个数组成的数列中查找的。因此被查找数列的长度实际上是3，那么参照点是比3稍小一点的Fibonacci数2.也就是这个被查找数列中的第2个数iList[7]，如下图所示：

Fibonacci查找作为二分查找的变种，在一般效率下肯定比顺序查找高，与二分查找方法不相上下。根据数据在数列中的分布状态，二分法和Fibonacci法很难说哪个更快一些。

代码实现

fibonacciSearch.py


from randomList import randomList
from quickSort import quickSort
import random
 
iList = quickSort(randomList(20))
 
def fibonacci(n):
    '''return the last element of the fibonacci sequence'''
    fList = [1, 1]
    while n > 1 :
        fList.append(fList[-1] + fList[-2])
        n -= 1
    return fList[-1]
 
def fibonacciSearch(iList, key):
    print("iList = %s" %str(iList))
    print("Find The number : %d" %key)
    iLen = len(iList)
    left = 0 
    right = iLen - 1
    indexSum = 0
 
    k = 1
    while fibonacci(k) -1 < iLen - 1: #fibonacci数列中的最后一个元素要比iList的长度稍微大一点
        k += 1
 
    while right - left > 1:
        mid = left + fibonacci(k - 1)
        if key < iList[mid] :
            right = mid - 1
            k -= 1
        elif key == iList[mid]:
            return mid
        else:
            left = mid + 1
            k -= 2
    if key == iList[left]:
        return left
    elif key == iList[right]:
        return right
    else:
        return -1
 
if __name__ == "__main__":
    keys = [random.choice(iList), random.randrange(min(iList), max(iList))]
    for key in keys:
        res = fibonacciSearch(iList, key)
        if res >= 0:
            print("%d is in the list, index is : %d\n" %(key, res))
        else:
            print("%d is not in the list\n" %key)