查找算法③-斐波那契查找算法/黄金分割查找算法

一、算法原理

        斐波那契查找算法又称黄金分割查找算法，它是在二分查找基础上根据斐波那契数列进行分割的一种衍生算法，简单来说，二分查找是一分为二进行查找，斐波那契查找是使用斐波那契数列进行分割查找。而斐波那契数列就是我们通常所说的黄金分割数列，它是1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、34 、 55 ... 一直延伸下去的数列，通项公式为： F(n) = F(n-1) + F(n-2)。

        我们知道黄金分割率是0.618，而粉波那契数列中的F(n-1) / F(n-2) ≈ 0.618 ， 比如5 / 8 = 0.625 ≈ 0.618， 34 / 55 = 0.6181818 ≈ 0.618 。

        所以，斐波那契查找算法也称黄金分割查找算法，二分查找是每次折半也就是按0.5进行折算，而斐波那契查找算法是按约等于0.618进行折算，速度上来说比二分查找算法快。

二、具体实现

# 自定义斐波那契查找函数
def fibonacci_search(data, target):
    # 斐波那契数列
    F = [
        1,
        1,
        2,
        3,
        5,
        8,
        13,
        21,
        34,
        55,
        89,
        144,
        233,
        377,
        610,
        987,
        1597,
        2584,
        4148,
        6765,
    ]
    # 待查找序列的左侧边
    left = 0
    # 待查找序列的右侧边
    right = len(data) - 1
    # 为了使查找表满足斐波那契特性，在表的最后添加几个相同的值
    # 这个值是原查找表的最后那个元素的值
    # 添加的个数由F[k] - 1 - right 决定
    k = 0

    while right > F[k] - 1:
        k += 1
    # 将i位置定位到right
    i = right

    while i < F[k] - 1:
        data.append(data[right])
        i += 1
    print("添加后的数据集：", data)

    # 算法主逻辑，count用于展示循环的次数。
    while left < right:
        # 防止F列表下标溢出
        if k < 2:
            mid = left
        else:
            mid = left + F[k - 1] - 1

        # 输出每次分割情况
        print("低位位置：%s,中间位置:%s,高位位置:%s" % (left, mid, right))
        if target < data[mid]:
            right = mid - 1
            k -= 1
        elif target > data[mid]:
            left = mid + 1
            k -= 2
        else:
            if mid <= right:
                return mid
            else:
                return right

    return False


# 即将查找的目标值
target = 77
# 待查找的数列
data = [18, 19, 22, 24, 56, 60, 66, 77, 88]

result = fibonacci_search(data, target)
print('目标数据', target, '的位置是', result)

运行后查找的过程如下：