python实现斐波那契查找

时间:2022-04-08 19:48:55

通过在网上找教程解释和看书,总结出一套比较简单易懂的代码实现。

斐波那契查找和二分查找一样,针对的是有序序列,在此前提下:

# 先创建一个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()