Python 程序重复输出

Question

我创建了二进制搜索，但遇到了问题。每当我运行 main( ) 时，当键等于 8、5、2 和 1 时，我只得到 None。我还试图让 bsearch return [=14 的索引=] integer_list 中的值，但它只是 return 中的 key_point。如果有人能让我知道出了什么问题，我将不胜感激。

def bsearch(integer_list, key_point, start, end):
    midpoint = (start + end) // 2
    if start >= end:
        return None
    elif integer_list[midpoint] == key_point:
        return key_point
    elif integer_list[midpoint] > key_point:
        return bsearch(integer_list, key_point, start, (midpoint - 1))
    elif integer_list[midpoint] < key_point:
        return bsearch(integer_list, key_point, (midpoint + 1), end)


def main( ):
    integer_list = [x + 1 for x in range(0, 10)]
    key = 11
    p = len(integer_list) - 1
    start = integer_list[0]
    end = integer_list[p]
    while key >= 1:
        bsearch(integer_list, key, start, end)
        print(bsearch(integer_list, key, start, end))
        key = key - 1

Answer 1

您在算法中多次混淆了索引和值。您的 base/found 案例应该返回中点，因为那是您找到它的地方，但您返回的是 key_point，您实际搜索的值。

同样，当您设置循环时，您将开始和结束值设置为列表开始和结束的内容，而不是开始和结束索引。如果您 test_list 使用的一组数字不仅仅是序列号 1-11，其中一些错误将变得更加明显。现在刚好排队。

Answer 2

首先，您将值而不是索引传递给函数：

start = 0
end = len(integer_list) - 1

其次你需要 return None 当开始和结束都颠倒了。不是当它们相等时

if start > end:
        return None

第三，你为什么要return你要搜索的值？这没有任何意义。您应该 return 元素的索引。

elif integer_list[midpoint] == key_point:
        return mid_point

最后，如果你想遵循几乎所有的搜索方法returns，当你找不到你要找的值时，你应该return -1，而不是None。这会让你省去一些麻烦。

if start > end:
        return -1

Answer 3

您有以下错误：

1) 从 main 调用 binary_search 包含 start = 1 andend = 10which should have beenstart = 0 和 end = 9（索引值） .我们根据索引找到所有的中点。

2) 只需检查 start > end，因为 start == end 是绝对正确的，而你得到 None 的情况都是由于这种情况。您因这种情况返回的所有情况实际上都是 integer_list[midpoint] == key_point 成立的情况。

这是更正后的代码：

def bsearch(integer_list, key_point, start, end):
    midpoint = (start + end) // 2
    if start > end:
        return None
    elif integer_list[midpoint] == key_point:
        return key_point
    elif integer_list[midpoint] > key_point:
        return bsearch(integer_list, key_point, start, (midpoint - 1))
    elif integer_list[midpoint] < key_point:
        return bsearch(integer_list, key_point, (midpoint + 1), end)


def main():
    integer_list = [x + 1 for x in range(0, 10)]
    key = 11
    p = len(integer_list) - 1
    start = integer_list[0]
    end = integer_list[p]
    while key >= 1:
        print(bsearch(integer_list, key, 0, p))
        key = key - 1
main()

希望对您有所帮助:)

Python 程序重复输出

Python repeated output from program

python

recursion

binary-search