为什么我的递归二进制搜索函数不返回任何内容？

debugcn 发表于 Dev

雷鬼蜥蜴

（...不要问这些数组的值，它们是拉丁美洲的食品品牌，与一些朋友开了个玩笑）。

def binSearch(arr, i, lower=0, upper=None):
    if upper is None:
        upper = len(arr)+1
    idx = (lower+upper)//2
    if arr[idx] == i:
        print(idx, arr[idx],'\n')
        #return idx
    elif arr[idx] != i and upper-lower<2:
        print("Not found \n")
        #return False
    elif arr[idx] < i:
        print(idx, arr[idx])
        binSearch(arr, i, idx, upper)
    elif arr[idx] > i:
        print(idx, arr[idx])
        binSearch(arr, i, lower, idx)

myArray = ["Chabona", "F-Nandito VII", "La Bichy", "Manaos", "Martín y Enzo", "Pitusas", "Trompis", "Ugi's", "VAMOS MANAOS", "Villamanaos"]

binSearch(myArray, "Manaos")
binSearch(myArray, "Coca-Cola")

该程序完全按照我的预期做–它输出以下内容：

5 Pitusas
2 La Bichy
3 Manaos 

5 Pitusas
2 La Bichy
1 F-Nandito VII
Not found

然而，这是我所得到的，当我注释掉所有打印语句使其返回idx或None代替，然后用更换电话print(binSearch(myArray, "Manaos"))和print(binSearch(myArray, "Coca-Cola"))：

None
None

它显然应该返回3，False但是什么也不会返回。我究竟做错了什么？

帕德拉克·坎宁安（Padraic Cunningham）

您不返回：

return binSearch(arr, i, lower, idx)

您还需要根据情况返回：

def binSearch(arr, i, lower=0, upper=None):
    if upper is None:
        upper = len(arr)+1
    idx = (lower+upper)//2
    if arr[idx] == i:
        print(idx, arr[idx],'\n')
        return idx # return 3/idx
    elif arr[idx] != i and upper-lower<2:
        print("Not found \n")
        return False  # return False
    elif arr[idx] < i:
        print(idx, arr[idx])
        return binSearch(arr, i, idx, upper)
    elif arr[idx] > i:
        print(idx, arr[idx])
        return binSearch(arr, i, lower, idx)

print(binSearch(myArray, "Manaos"))
print(binSearch(myArray, "Coca-Cola"))

5 Pitusas
2 La Bichy
3 Manaos 

3
5 Pitusas
2 La Bichy
1 F-Nandito VII
Not found 

False