Python写写出斐波那契二分检索,即使用斐波那契数列二分有序序列,查找某给定元素,找到返回下标,找不到返回-1
时间: 2024-03-07 22:50:08 浏览: 16
以下是使用斐波那契数列实现的二分检索算法的 Python 代码:
```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。