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新手,如有不对的地方请指正。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/a53f878ad050a0d651198e8e866fabd0.html