时间戳

首页 > 解决方案 > 执行二进制搜索时列出索引超出范围错误

python - 执行二进制搜索时列出索引超出范围错误

问题描述

我试图创建一个函数，它接受一个有序的数字列表和一个给定的数字，并决定给定的数字是否在列表内。我正在尝试使用二进制搜索来完成此任务。

我有两个步骤：

首先，我list1只取list1小于给定数字的数字，然后将这些数字附加到一个新列表中，称为newlist.

接下来，在while循环中，我基本上是取出所有小于中间数字的数字newlist并将它们删除，重复该过程多次，直到newlist. 从那里，我会将该数字与给定的数字进行比较。我的代码如下所示。

list1 = [1, 3, 5, 6, 8, 14, 17, 29, 31]
number = 7

def func(list1, number):
    newlist = []
    for x in list1:
        if x < number:
            newlist.append(x)
        else:
            continue

    while len(newlist) > 1:
        for x in range(0, len(newlist) - 1):
            if newlist[x] < newlist[round(len(newlist) / 2)]:
                newlist.remove(newlist[x])
            else:
                continue

    if newlist[0] == number:
        return True
    else:
        return False

print(func(list1, number))

我在第 36 行 ( if newlist[x] < newlist[round(len(newlist) / 2)]:) 收到错误，表明列表索引超出范围。我认为问题在于随着newlist越来越小，x设置的值range(0, len(newlist) - 1)保持不变？？如果是这种情况，我不确定如何补救。非常感谢提前。

标签： pythonlistwhile-loop

解决方案

问题就在这里：

for x in range(0, len(newlist) - 1):
    if newlist[x] < newlist[round(len(newlist) / 2)]:
        newlist.remove(newlist[x])

首先，您正在遍历列表

[0, 1, 2, ..., len(newlist) - 1]

这个列表是在你开始循环时生成的，这意味着如果len(newlist)一开始是 7，那么列表将永远上升到 6，无论是否从 中删除东西newlist，你稍后会这样做。这就是导致您的错误的原因，因为在某些时候您已经删除了足够的元素，以至于您的列表现在是三个元素，但是 python 正在尝试访问第五个元素，因为它正在迭代的列表不是newlist，而是[0, 1, 2, 3, 4, 5, 6].

要解决此问题，您可以（例如）将 for 循环替换为：

x = 0
while x < len(newlist - 1):
    if newlist[x] < newlist[round(len(newlist) / 2)]:
        newlist.pop(x)  # simple way of saying "remove item at index x"

这本质上是for在 python 中执行 C 或 Java 样式循环的方式，并且将避免此类问题。

我也了解您的代码中的逻辑存在问题，上述评论之一已指出这一点，并且更能触及您潜在问题的核心，但这至少可以解释为什么此错误发生在第一名，所以也许以后对你有帮助

推荐阅读