import random

#source为待查找数组，key为要查找的数
def fibonacciSearch(source,key):
    #生成裴波那契数列
    fib = [0,1]
    for i in range(1,36):
        fib.append(fib[-1]+fib[-2])

    #确定待查找数组在裴波那契数列的位置
    k = 0
    n = len(source)

    #此处 n>fib[k]-1 也是别有深意的
    #若n恰好是裴波那契数列上某一项，且要查找的元素正好在最后一位，此时必须将数组长度填充到数列下一项的数字
    while(n > fib[k]-1):
        k = k + 1
    
    #将待查找数组填充到指定的长度
    for i in range(n,fib[k]):
        a.append(a[-1])

    low,high = 0,n-1

    while(low <= high):

        #获取黄金分割位置元素下标
        mid = low + fib[k-1] - 1
        
        if(key < a[mid]):
            #若key比这个元素小,则key值应该在low至mid-1之间，剩下的范围个数为F(k-1)-1
            high = mid - 1
            k = k -1
        elif(key > a[mid]):
            #若key比这个元素大,则key至应该在mid+1至high之间，剩下的元素个数为F(k)-F(k-1)-1=F(k-2)-1
            low = mid + 1
            k = k - 2
        else:
            if(mid < n):
                return mid
            else:
                return n-1

    return -1


### 函数测试 ###

#生成待查找的数组
a = [random.randint(1,100000) for x in range(0,33)]
a.append(673990)
a.sort()

#待查找的数
key = 673990

#输出查找到的位置下标
print(fibonacciSearch(a,key))