本文共 2233 字，大约阅读时间需要 7 分钟。

一、含义

斐波那契数列（Fibonacci）又称黄金分割数列，指的是这样一个数列：1,1,2,3,5,8,13,21,…

二、输出结果

三、代码实现

import randomimport timeitdef randomList(n):    iList = []    for i in range(n):        iList.append(random.randrange(0,1000))    return iListdef quicksort(iList):    if(len(iList)<=1):        return iList    left = []    right = []    for i in iList[1:]:        if i<=iList[0]:            left.append(i)        else :            right.append(i)     return quicksort(left)+[iList[0]]+quicksort(right)def fibonacci(n):    iList = [1,1]    k = n;    while(k>1):        #获取的斐波那契数列第n位数据，即要查找列表的位置        #iList[-1]、iList[-2]表示列表最后一位数的前两位数据        iList.append(iList[-1] + iList[-2])        k -= 1    return iList[-1]def fibonacciSearch(iList,key):    ilen = len(iList)    left = 0    right = ilen - 1    if(ilen == 0):        return -1    #########斐波那契数列的长度k#########    k = 1    while fibonacci(k)-1 < ilen-1:        k += 1    ###################################    while right - left > 1:        #20个数的数列查找，斐波那契数列为[1 1  2 3 5 8 13 21]        #k = 7时，fibonacci(k-1)的值为13        #因此第一个mid=14,14表示查询数据的位置        mid = left +fibonacci(k-1)        if key < iList[mid]:            right = mid-1            k -= 1        elif key > iList[mid]:            left = mid+1             k -=2        else:            return mid    ##################################    if(key == iList[right]):        return right    elif(key == iList[left]):        return left    else:        return -1if __name__ == "__main__":    iList = quicksort(randomList(20))    print(iList)    keys=[random.choice(iList),random.randrange(min(iList),max(iList))]    for key in keys:        num = fibonacciSearch(iList,key)        if(num>=0):            print("%d number is %d\n"%(key,num))        else:            print("%d the key number is not find\n"%key)    #print(timeit.timeit("fibonacciSearch(iList，key)","from __main__ import selectsort,iList",number=100))