LeetCode 斐波那契搜索题解

LeetCode 斐波那契搜索题解题目描述实现斐波那契搜索算法在一个有序整数数组中查找目标值。示例输入[11, 12, 22, 25, 34, 64, 90]目标值22输出2目标值在数组中的索引解题思路方法斐波那契搜索思路斐波那契搜索的核心思想是利用斐波那契数列来确定搜索位置从而减少比较次数。具体步骤找到一个大于数组长度的斐波那契数 F(k)。将数组长度扩展到 F(k)不足部分用数组最后一个元素填充。使用斐波那契数列来确定搜索位置pos min(i F(k-2) - 1, n - 1)其中 i 是当前搜索区间的起始位置。比较搜索位置的元素与目标值如果搜索位置的元素等于目标值返回搜索位置的索引。如果搜索位置的元素大于目标值调整搜索区间为左半部分。如果搜索位置的元素小于目标值调整搜索区间为右半部分。重复步骤 3-4直到找到目标值或搜索区间为空。复杂度分析时间复杂度O(log n)其中 n 是数组的长度。斐波那契搜索的时间复杂度与二分搜索相同。空间复杂度O(1)只需要常数级的额外空间。代码实现方法斐波那契搜索# 斐波那契搜索 def fibonacci_search(arr, target): n len(arr) if n 0: return -1 # 初始化斐波那契数列 fib_k_minus_2 0 # F(k-2) fib_k_minus_1 1 # F(k-1) fib_k fib_k_minus_1 fib_k_minus_2 # F(k) # 找到一个大于数组长度的斐波那契数 while fib_k n: fib_k_minus_2 fib_k_minus_1 fib_k_minus_1 fib_k fib_k fib_k_minus_1 fib_k_minus_2 # 初始化为 -1表示尚未使用过的位置 offset -1 # 使用斐波那契数列来确定搜索位置 while fib_k 1: # 计算搜索位置 i min(offset fib_k_minus_2, n - 1) if arr[i] target: # 目标值在右半部分 fib_k fib_k_minus_1 fib_k_minus_1 fib_k_minus_2 fib_k_minus_2 fib_k - fib_k_minus_1 offset i elif arr[i] target: # 目标值在左半部分 fib_k fib_k_minus_2 fib_k_minus_1 fib_k_minus_1 - fib_k_minus_2 fib_k_minus_2 fib_k - fib_k_minus_1 else: # 找到目标值 return i # 检查最后一个元素 if fib_k_minus_1 and arr[offset 1] target: return offset 1 return -1 # 测试 def test_fibonacci_search(): arr [11, 12, 22, 25, 34, 64, 90] print(fibonacci_search(arr, 22)) # 输出2 print(fibonacci_search(arr, 100)) # 输出-1 print(fibonacci_search(arr, 11)) # 输出0 if __name__ __main__: test_fibonacci_search()测试用例测试用例 1基本情况输入[11, 12, 22, 25, 34, 64, 90]目标值22输出2测试用例 2目标值不存在输入[11, 12, 22, 25, 34, 64, 90]目标值100输出-1测试用例 3目标值在第一个位置输入[11, 12, 22, 25, 34, 64, 90]目标值11输出0总结斐波那契搜索是一种高效的搜索算法它利用斐波那契数列来确定搜索位置从而减少比较次数。斐波那契搜索适用于有序数组其时间复杂度为 O(log n)与二分搜索相同。斐波那契搜索的核心思想是利用斐波那契数列来确定搜索位置从而减少比较次数。掌握斐波那契搜索的原理和实现对于理解搜索算法的基本思想非常重要。