再帰バイナリ検索プログラムで何が問題になっていますか？

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

編集：このプログラムは、もともと文字の値を見つけることとしました。ポジションは手紙であると考えられ、私はちょうどreturn.indexそれを最後にします。しかし、わかりやすく分かりやすくするために、私は最後にreturnステートメントを変更しました。それはまだの代わりにと同じ結果で終わります。。

Answer 1

アルゴリズムを初めて呼び出すと、Nが配列の中央にあります。したがって、このライン

position = lst[midpoint] 

はセットNからposition。その後、あなたは値を決して変更しないでくださいはpositionです！

あなたはへの2本の再帰的なラインを変更する必要があります。問題はここでは、構文

return position  

た

return binSearch(lst, what) 

Answer 2

は私が

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)です。この新しい内部binSearch呼び出しの 'position'変数は、外部呼び出しの位置に決して影響しません。このように関数を記述したい場合は、その行は実際にはposition = binSearch(lst, what)のようになります。その場合、外部呼び出しの位置を正しく更新する必要があります。