Python实现裴波那契查找详解
裴波那契查找（Fibonacci Search）是利用黄金分割原理实现的查找方法。
斐波那契查找的核心是：
1.当key == a[mid]时，查找成功；
2.当key < a[mid]时，新的查找范围是low至mid-1, 此时范围个数为F[k-1] - 1个，即数组左边的长度；
3.当key < a[mid]时，新的查找范围是mid+1至high，此时范围个数为F[k-2] - 1个，即数组右边的长度；
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))
Python新手，如有不对的地方请指正。