手机版
你好,游客 登录 注册 搜索
背景:
阅读新闻

Python实现裴波那契查找详解

[日期:2017-04-20] 来源:Linux社区  作者:praglody [字体: ]

裴波那契查找(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新手,如有不对的地方请指正。

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-04/142989.htm

linux
相关资讯       裴波那契查找 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款