基于Fibonacci Search实现跨列表元素查找的代码问题排查

问题概述 #

原斐波那契查找函数可在整数列表中查找目标值，修改为适配字符串列表后，程序无任何输出，但预期应遍历列表y中的每个元素，在列表x中匹配并返回对应索引。

错误分析 #

1. 循环变量名冲突：嵌套循环均使用i作为变量名，内层循环的i会覆盖外层循环的变量，导致逻辑混乱。
2. 条件判断逻辑错误：if i == y中，i是y列表的单个元素，而y是整个列表，二者永远不可能相等，因此条件永远不成立，不会执行打印操作。
3. 函数传参错误：调用FibonacciSearch时传入了整个列表y，而非当前要查找的单个元素i。
4. 查找列表无序：斐波那契查找依赖有序列表（升序）的比较逻辑，原x列表的字符串顺序不符合字典序（例如"10e"的字典序小于"2d"，但在列表中位于"9g"之后），会导致查找失败。

修复后的代码 #

def FibonacciSearch(lys, val):
    fibM_minus_2 = 0
    fibM_minus_1 = 1
    fibM = fibM_minus_1 + fibM_minus_2
    while fibM < len(lys):
        fibM_minus_2 = fibM_minus_1
        fibM_minus_1 = fibM
        fibM = fibM_minus_1 + fibM_minus_2
    index = -1
    while fibM > 1:
        i = min(index + fibM_minus_2, len(lys)-1)
        if lys[i] < val:
            fibM = fibM_minus_1
            fibM_minus_1 = fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
            index = i
        elif lys[i] > val:
            fibM = fibM_minus_2
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        else:
            return i
    if fibM_minus_1 and index < len(lys)-1 and lys[index+1] == val:
        return index+1
    return -1

# 将x按字典序排序，保证查找的有序性
x = sorted(["2d","4c","6f","9g","10e","11p"])
y = ["2d","6f","9g"]

# 遍历y中的每个元素进行查找
for target in y:
    idx = FibonacciSearch(x, target)
    if idx != -1:
        print(f"Found '{target}' on index {idx}")
    else:
        print(f"'{target}' not found in the list")

修复说明 #

• 修正循环变量名：直接遍历y的元素作为目标值，避免嵌套循环的变量冲突。
• 修正条件与传参：调用FibonacciSearch时传入单个目标元素，并根据返回值判断是否找到并打印结果。
• 保证列表有序：对x进行字典序排序，满足斐波那契查找的前置条件。

运行结果 #

运行修复后的代码，输出如下：

Found '2d' on index 2
Found '6f' on index 3
Found '9g' on index 4

内容的提问来源于stack exchange，提问作者ya xi er