我的二进制搜索函数返回None，我不知道为什么

Question

我正在用Python实现二进制搜索，我为此创建了一个函数，但是不知何故，我介于两者之间。我的功能返回“ None”作为输出，但我不知道为什么这样做。我的代码在这里：

x = [1,2,3,4,5,6,7,8,9,10]
y = 9

def bin_search(s_list, key):
    print(s_list)
    m = s_list[len(s_list)//2]
    if m == key:
        return 1
    elif m < key:
        bin_search(s_list[s_list.index(m)+1:],key)
    else:
        bin_search(s_list[0:s_list.index(m)],key)

print（bin_search（x，y））它给出以下输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[7, 8, 9, 10]
None

Answer 1

[当您进行递归调用时，请确保将值return传递给堆栈，然后再将其传递给调用方。仅写入bin_search(...)会忽略返回值。

if m == key:
    return 1
elif m < key:
    return bin_search(s_list[s_list.index(m)+1:],key)
else:
    return bin_search(s_list[0:s_list.index(m)],key)

Answer 2

这是因为您的代码按预期工作：

def bin_search(s_list, key):
    print(s_list)
    m = s_list[len(s_list)//2]
    if m == key:
        print('if')
        return 1
    elif m < key:
        print('elif')
        print(s_list[s_list.index(m)+1:])
        bin_search(s_list[s_list.index(m)+1:],key)
    else:
        print('else')
        print(s_list[0:s_list.index(m)])
        bin_search(s_list[0:s_list.index(m)],key)

添加调试打印有助于查明正在发生的事情。

print( bin_search(x, y)) 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
elif
[7, 8, 9, 10]
[7, 8, 9, 10]
if
None

所以实际上有一个实例，其中m == key。

Answer 3

我想补充@Greg的答案，如果您想将1恢复为主调用函数，则应在递归后返回return value。喜欢：

def bin_search(s_list, key):
    print(s_list)
    m = s_list[len(s_list)//2]
    if m == key:
        return 1
    elif m < key:
        return bin_search(s_list[s_list.index(m)+1:],key)
    else :
        return bin_search(s_list[0:s_list.index(m)],key)

x = [1,2,3,4,5,6,7,8,9,10]
y = 7    
print( bin_search(x, y))

您还应处理找不到密钥的情况。