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

好的，这里是斐波那契二分检索的 Python 实现：

def fibonacci_search(arr, x):
    n = len(arr)
    fib2 = 0
    fib1 = 1
    fib = fib2 + fib1
    while fib < n:
        fib2 = fib1
        fib1 = fib
        fib = fib2 + fib1
    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

该算法的时间复杂度为 $O(\log n)$，其中 $n$ 为有序序列的长度。

相关问题

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

以下是使用斐波那契数列实现的二分检索算法的 Python 代码：

def fibonacci_search(arr, x):
    # 生成斐波那契数列，使得其最后一个元素大于等于要查找的数组长度
    fib_nums = [0, 1]
    while fib_nums[-1] < len(arr):
        fib_nums.append(fib_nums[-1] + fib_nums[-2])
    # 初始化左侧和右侧的位置
    left, right = 0, len(arr) - 1
    # 遍历斐波那契数列
    while fib_nums:
        # 从斐波那契数列中取出当前的数值
        fib = fib_nums.pop()
        # 计算中间位置的索引
        mid = min(left + fib, len(arr) - 1)
        # 如果要查找的元素在中间位置的左侧，则舍弃右侧部分
        if x < arr[mid]:
            right = mid - 1
        # 如果要查找的元素在中间位置的右侧，则舍弃左侧部分
        elif x > arr[mid]:
            left = mid + 1
        # 否则，找到了要查找的元素
        else:
            return mid
    # 如果遍历完整个斐波那契数列仍然没有找到要查找的元素，则返回 -1
    return -1

在这个算法中，我们首先生成一个斐波那契数列，使得其最后一个元素大于等于要查找的数组的长度。然后，我们使用这个斐波那契数列来确定要查找的元素的位置。我们使用左侧和右侧的索引来表示要查找的部分，然后从斐波那契数列中取出一个数值，将其加到左侧的索引上，得到中间位置的索引。如果要查找的元素在中间位置的左侧，则舍弃右侧部分；如果要查找的元素在中间位置的右侧，则舍弃左侧部分；否则，找到了要查找的元素。如果遍历完整个斐波那契数列仍然没有找到要查找的元素，则返回 -1。

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。