python 写出斐波那契二分检索，即使用斐波那契数列二分有序序列，查找某给定元素，找到返回下标，找不到返回-1

好的，下面是代码实现：

def fibonacci_search(arr, x):
    # 生成斐波那契数列
    fib = [0, 1]
    while fib[-1] < len(arr):
        fib.append(fib[-1] + fib[-2])

    # 初始化指针
    low, high = 0, len(arr) - 1
    k = len(fib) - 1

    # 进行斐波那契查找
    while low <= high:
        mid = low + fib[k - 1] - 1
        if x < arr[mid]:
            high = mid - 1
            k -= 1
        elif x > arr[mid]:
            low = mid + 1
            k -= 2
        else:
            return mid

    return -1

其中，arr表示有序序列，x表示要查找的元素。函数先生成斐波那契数列，然后初始化指针，进行斐波那契查找。如果找到了，返回元素下标；如果没有找到，返回-1。

相关问题

Python写出斐波那契二分检索，即使用斐波那契数列二分有序序列，查找某给定元素，找到返回下标，找不到返回-1

以下是一个基于斐波那契数列的二分查找程序的实现：

def fibonacci_search(arr, x):
    n = len(arr)
    fib2 = 0
    fib1 = 1
    fib = fib2 + fib1
    
    # Find the smallest Fibonacci number greater than or equal to n
    while fib < n:
        fib2 = fib1
        fib1 = fib
        fib = fib2 + fib1
    
    # Marks the eliminated range from front
    offset = -1
    
    # While there are elements to be inspected
    while fib > 1:
        # Check if fib2 is a valid location
        i = min(offset + fib2, n - 1)
        
        # If x is greater than the value at index fib2, cut the subarray array from offset to i
        if arr[i] < x:
            fib = fib1
            fib1 = fib2
            fib2 = fib - fib1
            offset = i
        
        # If x is less than the value at index fib2, cut the subarray after i+1
        elif arr[i] > x:
            fib = fib2
            fib1 = fib1 - fib2
            fib2 = fib - fib1
        
        # If x is equal to the value at index fib2, return the index
        else:
            return i
    
    # Compare the last element with x
    if fib1 and offset < n-1 and arr[offset+1] == x:
        return offset + 1
    
    # If the element was not found, return -1
    return -1

该函数接受一个数组和一个要查找的值x作为参数，并返回x在数组中的下标，如果x不存在于数组中，则返回-1。

该算法的时间复杂度为 O(log n)。虽然它比传统的二分查找稍微慢一些，但它的优点是可以在没有指针引用的情况下进行搜索，因此它可以用于非随机存取的数据结构（例如磁盘存储）。此外，该算法还具有与二分查找相同的优点，即时间复杂度为 O(log n)。

用Python写出斐波那契二分检索，即使用斐波那契数列二分有序序列，查找某给定元素，找到返回下标，找不到返回-1

好的，我来给你写一个斐波那契二分检索的 Python 函数：

def fibonacci_search(arr, x):
    n = len(arr)
    fib2 = 0
    fib1 = 1
    fib = fib1 + fib2

    while fib < n:
        fib2 = fib1
        fib1 = fib
        fib = fib1 + fib2

    offset = -1

    while fib > 1:
        i = min(offset + fib2, n - 1)

        if arr[i] < x:
            fib = fib1
            fib1 = fib2
            fib2 = fib - fib1
            offset = i
        elif arr[i] > x:
            fib = fib2
            fib1 = fib1 - fib2
            fib2 = fib - fib1
        else:
            return i

    if fib1 and arr[offset + 1] == x:
        return offset + 1

    return -1

这个函数接收一个有序序列 `arr` 和要查找的元素 `x`，返回 `x` 在 `arr` 中的下标，如果没找到则返回 -1。

函数内部使用斐波那契数列生成一个递增的序列，然后在这个序列上执行二分查找。因为斐波那契数列的前两项是 1 和 1，所以初始的 fib2 和 fib1 分别设置为 0 和 1，fib 初始值为 2，然后不断计算 fib2、fib1、fib，直到 fib 大于等于序列长度，这样就生成了一个不小于序列长度的斐波那契数。

然后使用 offset 记录上一次查找的位置，每次在斐波那契数列上取一个数 i，如果 arr[i] 小于要查找的元素 x，则将 offset 设置为 i，并将 fib1 和 fib2 更新为下一次查找的范围，然后继续在斐波那契数列上取一个数，直到找到了 x 或者 fib 小于等于 1。

如果找到了 x，则返回 i；如果 fib1 不为 0，且 arr[offset+1] 等于 x，则返回 offset+1；否则返回 -1。