Python中如何实现斐波那契查找算法

def fibonacciSearch(arr, x):
    # 定义斐波那契数列
    fibList = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
    n = len(arr)
    # 初始化斐波那契数列的下标
    fibIndex = 0
    while fibList[fibIndex] < n:
        fibIndex += 1
    # 定义辅助数组
    assistList = [-1] * fibList[fibIndex]
    for i in range(n):
        assistList[i] = arr[i]
    # 斐波那契查找
    low = 0
    high = n - 1
    while low <= high:
        mid = low + fibList[fibIndex - 1] - 1
        if x < assistList[mid]:
            high = mid - 1
            fibIndex = fibIndex - 1
        elif x > assistList[mid]:
            low = mid + 1
            fibIndex = fibIndex - 2
        else:
            if mid <= high:
                return mid
            else:
                return -1
    return -1

# 测试代码
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(fibonacciSearch(arr, 9))  # 打印 4
print(fibonacciSearch(arr, 8))  # 打印 -1
print(fibonacciSearch(['p', 'i', 'd', 'a', 'n', 'c', 'o', 'd', 'e', '.', 'c', 'o', 'm'], 'o'))  # 打印 6
print(fibonacciSearch(['p', 'i', 'd', 'a', 'n', 'c', 'o', 'd', 'e', '.', 'c', 'o', 'm'], 'z'))  # 打印 -1
print(fibonacciSearch(['皮', '蛋', '编', '程'], '编'))  # 打印 2
print(fibonacciSearch(['皮', '蛋', '编', '程'], '鸡'))  # 打印 -1