python - 我的递归二分搜索程序出了什么问题？

Question

我似乎无法弄清楚为什么我的代码一直返回 N 而不是 R。在进入 return 语句之前，我已经测试了该字母是什么，正如您在输出图像中看到的那样，它应该是 R。然而，它继续返回N，如图所示，我不知道为什么它会这样做......我已经尝试过手动跟踪该过程，但最终仍然得到 R。我在代码中添加了一些注释，以便您查看和理解我的想法。我还在底部添加了输出的图片。

输入:['A'、'B'、'C'、'D'、'E'、'F'、'G'、'H'、'I'、'J'、' K'、'L'、'M'、'N'、'O'、'P'、'Q'、'R'、'S'、'T'、'U'、'V'、'W' , 'X', 'Y', 'Z']

def binSearch(lst, what):
    position = ""
    original_lst = lst[:]
    if (position == what): # Doesn't do anything since no recursive is made when position is equal to R.
        return original_lst.index("%s" %position)
    else:
        midpoint = (len(lst))//2
        position = lst[midpoint]
        print("Looking at", position)
        if position > what:
            lst = lst[:midpoint]
            binSearch(lst, what)
        elif position < what:
            lst = lst[midpoint:]
            binSearch(lst, what)
        elif position == what: # Removable. Just Testing and seeing what position it results as.
            print("Position it ends up in:", position) # when I replace this later, I probably should use a binSearch(). I think?
        else:
            return -1 # this is for if the letter not found.
    return position # Why does it return N... instead of R? This originally was suppose to find the index of the letter on the list. I adjusted it to see what letter the program was searching for instead. It still results in the same problem if I change it to look for the index of letter instead as it looks for **N** instead of **R**
# just to clarify, I was aiming to use return original_lst.index("%s" %position) to find the index of the letter. I just changed it to see what letter its returning instead. 
    
    

lst = []
while True:
   val = input()
   if val == "exit":
      break
   lst.append(val)

print(lst)
lst.sort()
print(lst)

what = input("Enter element to search for:")
print(what)
where = binSearch(lst, what)
if where != -1: 
    print("Found at position", where)
else:
    print("Not found")

Picture of Output

编辑:这个程序最初是为了找到字母的值。位置应该是这封信，我只是在最后 return.index 它。然而，为了使其更具可读性和更容易理解，我更改了最后的 return 语句。它最终仍会得到与返回 N 而不是 R 相同的结果。

Answer 1

第一次调用该算法时，N 位于数组的中间。所以这一行

position = lst[midpoint]

将位置设置为N。然后，您永远不会更改位置的值!

您应该将两行递归行更改为:

return binSearch(lst, what)