时间戳

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

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

问题描述

这是我的代码：

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 将返回 999 但 998 将返回：

RecursionError: maximum recursion depth exceeded in comparison

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

标签： pythonpython-3.xalgorithmsortingbinary-search

解决方案

mid = min + (max - 1) // 2大概应该是(min + max) // 2。此外，您的代码应该有一个返回值的基本情况，比如-1该元素是否在列表中不存在。就像if min > max: return -1在搜索功能的开头一样。

推荐阅读