我正在尝试为学校项目创建二进制搜索程序，但某些数字会导致无限递归

Question

这是我的代码：

list = []
line = 50

def genList(list):
    i = 0
    while i < 1000:
        list.append(i)
        i += 1
    return list

def displayList(list, line):
    i = 0
    while i < 1000:
        if i != 0 and i % line == 0:
            print('\n')
        print('{0:03}'.format(list[i]), end = ' ')
        i += 1
    print('\n')

def binarySearch(min, max, list, goal):
    mid = min + (max - 1) // 2
    if list[mid] == goal:
        return mid
    elif list[mid] > goal:
        return binarySearch(min, mid - 1, list, goal)
    else:
        return binarySearch(mid + 1, max, list, goal)

genList(list)
displayList(list, line)
goal = int(input('What number do you want to find, from 0 to 999?\n'))

result = binarySearch(0, len(list) - 1, list, goal)
print(result)

...就像我说的，某些数字有效但其他数字无效，例如 999 将 return 999 但 998 将 return:

RecursionError: maximum recursion depth exceeded in comparison

有人知道它有什么问题吗？我有点不知所措...

Answer 1

mid = min + (max - 1) // 2 应该是 (min + max) // 2。此外，您的代码应该有一个 returns 值的基本情况，如果列表中不存在该元素，则说 -1 。 if min > max: return -1 之类的东西就在搜索功能的开头。

Answer 2

这一行肯定是错误的：

mid = min + (max - 1) // 2

也许你的意思是（正如@Nikolaos Chatzis 指出的那样）

mid = min + (max - min) // 2

但以下操作也有效，需要少一项操作：

mid = (min + max) // 2

此外，如果 minval > maxval（如果您搜索的值不在列表中）

，您应该中止递归

我没看你能不能做得更好。但这应该有效

def binarySearch(minval, maxval, list_, goal):
    mid = (minval + maxval) // 2
    # print(minval, maxval, mid, goal)  # uncomment for debugging
    if minval > maxval:  # couldn't find search value
        return None
    if list_[mid] == goal:
        return mid
    elif list_[mid] > goal:
        return binarySearch(minval, mid - 1, list_, goal)
    else:
        return binarySearch(mid + 1, maxval, list_, goal)

也不要犹豫，添加用于调试的打印语句（或日志）。

这使得问题所在很明显。

您还可以做的是运行一些简单的测试代码，以证明它适用于所有情况：

for v in range(1000):
    assert binarySearch(0, len(list_) -1, list_, v) == v

同时作为一般性建议，不要遇到有趣或奇怪的错误。

min、max 和 list 都是 python 关键字。您可以通过不使用具有这些名称的变量来避免有趣的惊喜。使用许多基本语法高亮器，它还使您的代码看起来更好。

不禁止将它们用作变量名，但我认为这不是一个好主意。

我正在尝试为学校项目创建二进制搜索程序，但某些数字会导致无限递归

I am attempting to create a binary search program for a school project, but certain numbers cause infinite recursion

python

sorting

algorithm

binary-search

python-3.x