我的递归二进制搜索程序有什么问题？

Question

我似乎无法弄清楚为什么我的代码一直 returning N 而不是 R。在转到 return 语句之前，我已经测试了字母的内容，正如您在输出图像中看到的那样，它应该是 R。然而，它继续 return 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]

将 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)。这个新的内部 binSearch 调用中的 'position' 变量绝不会影响外部调用中的位置。如果您想以这种方式编写函数，那么该行实际上应该是这样的：position = binSearch(lst, what)。然后应该正确更新外部调用中的位置。

我的递归二进制搜索程序有什么问题？

What is wrong with my Recursive Binary-Search program?

python

recursion

binary-search

python-3.x