通过在网上找教程解释和看书，总结出一套比较简单易懂的代码实现。
斐波那契查找和二分查找一样，针对的是有序序列，在此前提下：
# 先创建一个Fibonacci函数 fib = lambda n: n if n < 2 else fib(n-1) + fib(n-2)
斐波那契查找，是通过利用斐波那契数列的值作为分割点，然后二分查找，相对于普通的二分查找，性能更优秀
def fib_search(arr, x):
left = 0
right = len(arr) - 1
# 计算fib的值，这个值是大于等于arr的长度的，所以使用时要对key-1
key = 0
while fib(key) < len(arr):
key += 1
while left <= right:
# 当x在分隔的后半部分时，fib计算的mid值可能大于arr长度
# 因为mid是索引位置，这里要取arr长度-1
mid = min(left + fib(key - 1), len(arr) - 1)
if x < arr[mid]:
right = mid - 1
key -= 1
elif x > arr[mid]:
left = mid + 1
key -= 2
else:
return mid
return "Not Found"
若x的值刚好是arr[0]，那么则会出现一种情况，即按照fibonacci数列的值依次对比，其中会出现如8,5,3,2,1,1,0这种索引，两个1就是重复了，所以大家看到的很多例子里，mid的计算是left + fib(key -1) - 1，这里最后的-1其实就是去掉索引重复值。
# 举个例子 arr = [0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99] x = 0 # 不加-1的mid值依次是8，5，3，2，1，1，0 # 加了-1的mid值依次是7，4，2，1，0
有兴趣的可以测试下代码
fib = lambda n: n if n < 2 else fib(n-1) + fib(n-2)
def fib_search(arr, x):
if len(arr) == 0:
return 'arr is None'
left = 0
right = len(arr) - 1
# 计算fib的值，这个值是大于等于arr的长度的，所以使用时要对key-1
key = 0
while fib(key) < len(arr):
key += 1
while left <= right:
# 当x在分隔的后半部分时，fib计算的mid值可能大于arr长度
# 因为mid是索引位置，这里要取arr长度-1
mid = min(left + fib(key - 1) - 1, len(arr) - 1)
if x < arr[mid]:
right = mid - 1
key -= 1
elif x > arr[mid]:
left = mid + 1
key -= 2
else:
return mid
return "Not Found"
def test_fib_search():
arr = [0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99]
x = 0 print(fib_search(arr, x))
if __name__ == '__main__':
test_fib_search()