Что не так с моей программой рекурсивного двоичного поиска?

Question

Я не могу понять, почему мой код продолжает возвращаться N вместо R. Я проверил, что будет за письмо, прежде чем перейти к оператору возврата, и, как вы можете видеть на изображении вывода, это должно быть 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

Edit: Эта программа была изначально предполагают, чтобы найти значение письма. Позиция должна была быть буквой, и я бы просто вернулся. Индекс это в конце. Однако, чтобы сделать его более понятным и понятным, я изменил оператор return в конце. Он по-прежнему заканчивается теми же результатами, что и в нем N вместо R.

Answer 1

При первом вызове алгоритм N находится в середине массива. Так эта линия

position = lst[midpoint] 

position наборы для N. Затем вы никогда не меняете значение из position!

Вы должны изменить две рекурсивные строки:

return binSearch(lst, what) 

Answer 2

Проблема была с синтаксисом

return position  

Вот что я получил

def binSearch(lst, what,low=0, high=None): 
    high = len(lst) if high is None else high 
    pos = int(low + (high-low)/len(lst)) 
    if (pos==len(lst)): 
    return False 
    elif (lst[pos]==what): 
    return pos 
    elif high==low: 
    return False 
    elif (lst[pos]<what): 
    return binSearch(lst, what, pos + 1, high) 
    else: 
    assert lst[pos] > what 
    return binSearch(lst, what, low, pos) 

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+1) #+1 because the index start from 0 
    print (lst[where]) 
else: 
    print("Not found") 

Надеется, что это помогает.

Answer 3

В первый раз через это вы нажмете эту строку кода: position = lst[midpoint] и таким образом установите положение на «N». Затем вы проходите процедуру поиска, но на каждой ветви вы выполняете: binSearch(lst, what). Переменная 'position' в этом новом внутреннем вызове binSearch никак не влияет на позицию во внешнем вызове. Если вы хотите написать функцию таким образом, то эта строка действительно должна выглядеть примерно так: position = binSearch(lst, what). Это должно затем правильно обновить позицию во внешнем вызове.