python斐波那契查找算法分享

cztanghao

最近在学习python算法，分享一下学习心得。这个板块excel的python求助比较少，希望能多起来，python能实现Excel的所有功能，等于excel函数加power query加vba，其中只是暂时不能实现vba的交互功能。还有希望python能单独起一个板块，毕竟以后是大势。最起码也不要放在vba的板块的子版块。
def fib_find(data,key):
    a, b = 1, 1
    F = [a]
    for i in range(20):
        a, b = b, a + b
        F.append(a)
    print(F)
    low=0
    high=len(data)-1
    k=0
    while high > F[k]-1:#应是high大于后者
        k+=1

    data=data+[data[high]]*(F[k]-1-high)
    print(data)

    while low <=high:
        if k<2:
            # mid=k
            mid=low #应该是low
        else:
            mid=low+F[k-1]-1

        if key<data[mid]: #大于还是小于方向不能错
            high=mid-1
            k-=1
        elif key>data[mid]:
            low=mid+1
            k-=2
        else:
            if mid<=high:
                return mid
            else:
                return high
    return -1




if __name__ == '__main__':
    data = [9,10,13,15,22,29,37,48,53]
    key=37
    print(fib_find(data,key))
斐波那契查找算法是一种利用斐波那契数列来分割已排序数组的搜索算法。其基本思想与二分查找类似，都是通过将搜索范围分成几部分来减少搜索的范围，但斐波那契查找在分割点的选择上使用了斐波那契数列。以下是该算法的完整解释：

首先准备一个斐波那契数列 F。这个数列需要满足条件：数列中最大的元素值要超过被搜索数组 data 中的元素个数。

初始化低位 low 为 0，高位 high 为 len(data) - 1。

确定斐波那契数列的下标 k，使得 F[k] 是大于等于 data 长度的最小斐波那契数。

如果 F[k] - 1 大于数组 data 的最高索引 high，则向 data 数组末尾添加元素，直到其长度达到 F[k] - 1。添加的元素值都是 data 中原本的最后一个元素值。

进行斐波那契查找的主要循环。在每次循环中，根据斐波那契数列确定中间位置 mid。如果 k 小于 2，则 mid 设为 low。否则，mid 为 low + F[k - 1] - 1。

比较 key 与 data[mid]。如果 key 小于 data[mid]，说明 key 应该位于当前中间位置的左侧，将 high 设置为 mid - 1，并将 k 减 1。如果 key 大于 data[mid]，说明 key 应该位于当前中间位置的右侧，将 low 设置为 mid + 1，并将 k 减 2。

如果 key 等于 data[mid]，则 key 已经被找到。如果 mid 的值小于等于 high，返回 mid 作为 key 的位置。否则，返回 high 作为 key 的位置。这种情况发生在当原始数组 data 被扩展后，mid 指向新增加的元素时。

如果循环结束，low 大于 high，说明 key 不在数组中，返回 -1表示没有找到。

沈默00

十分赞同LZ所言，多一些python的基础学习方法和经验，把版块支撑起来

495153973

我就是从python版块进来的，才20个贴，还有18年的归类了进来…………今天就是突然进论坛，发现好像多了个python版块，以前没见过

世界客都

不错，学习了。谢谢。