为什么我的递归二进制搜索函数没有返回任何东西？

Question

（…不要问数组值，它们是拉丁美洲的食品品牌，成为一些朋友的内部笑话）。你知道吗

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

然而，当我注释掉所有的print语句，让它返回idx或None，然后用print(binSearch(myArray, "Manaos"))和print(binSearch(myArray, "Coca-Cola"))替换调用时，我得到的结果是：

None
None

它显然应该返回3和False，但它什么也不返回。我做错什么了？你知道吗

Answer 1

你不会回来的：

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