写出斐波那契二分检索,即使用斐波那契数列二分有序序列,查找某给定元素,找到返回下标,找不到返回-1python实现
时间: 2024-02-05 10:02:53 浏览: 22
好的,这里是斐波那契二分查找算法的 Python 实现:
```python
def fib_search(arr, x):
# 先生成斐波那契数列
fib_m_minus_2, fib_m_minus_1, fib_m = 0, 1, 1
while fib_m < len(arr):
fib_m_minus_2 = fib_m_minus_1
fib_m_minus_1 = fib_m
fib_m = fib_m_minus_1 + fib_m_minus_2
# 从斐波那契数列的第三个元素开始,逆序遍历斐波那契数列中的元素
offset = -1
while fib_m > 1:
i = min(offset + fib_m_minus_2, len(arr) - 1)
if arr[i] < x:
fib_m, fib_m_minus_1 = fib_m_minus_1, fib_m_minus_2
fib_m_minus_2 = fib_m - fib_m_minus_1
offset = i
elif arr[i] > x:
fib_m, fib_m_minus_1 = fib_m_minus_2, fib_m_minus_1 - fib_m_minus_2
fib_m_minus_2 = fib_m - fib_m_minus_1
else:
return i
# 如果在斐波那契数列的第一个元素处找到了目标元素,直接返回
if fib_m_minus_1 and arr[offset + 1] == x:
return offset + 1
# 目标元素不存在于数组中
return -1
```
这个算法的时间复杂度为 O(log n),其中 n 是数组的长度。