Python达成裴波那契查找详解
发布时间：2021-11-15 15:34:07 所属栏目：教程 来源：互联网
导读：裴波那契查找（Fibonacci Search）是利用黄金分割原理实现的查找方法。 斐波那契查找的核心是： 1.当key == a[mid]时，查找成功； 2.当key a[mid]时，新的查找范围是low至mid-1, 此时范围个数为F[k-1] - 1个，即数组左边的长度； 3.当key a[mid]时，新的查找
|
裴波那契查找（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新手，如有不对的地方请指正。  （编辑：济南站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
