0

使用此二进制搜索功能，我收到较大数据集的索引错误。当我输入一个较小的数据集，即 [1,2,3,4,5] 搜索 5 时，算法按预期运行。但是，当我使用下面的文本时，使用空参数列表（分隔符字符为 ''）调用字符串对象的 split 方法并将字符串分解为每个元素都是字符串的列表值，然后搜索单词 '过失'我最终得到以下错误：

IndexError : 列表索引超出范围

非常感谢您的帮助。谢谢你。

字符串：1. Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua。Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat。Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur。Exceptioneur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est labourum。

代码：http: //ideone.com/TXVfQA

def binary_search(l,skey,start,stop):
    length = (stop - start) + 1 # length of search space
    middle = start + (length / 2)
    mid_val = l[middle]
    if skey == mid_val:
        return middle
    elif skey > middle:
        return binary_search(l,skey,(middle + 1),stop)
    else:
        return binary_search(l,skey,start,(middle - 1))
4

2 回答 2

0

您永远不会检查是否stop小于start. 您的递归调用将轻松创建该条件。

于 2013-05-07T22:57:47.173 回答
0

这个算法有几个问题。

首先，如果您请求的项目小于列表 ( skey < l[start]) 中的最小项目，则它会循环。其次，当skey not in l[start:stop], then search 因索引超出范围而下降。

对于列表中未显示元素的情况，您没有适当的行为。例如，None如果未找到元素，您可以返回。您的代码可以这样修复：

def binary_search(l, skey, start, stop):
    # possible answer is always in interval [start, stop)
    while start + 1 != stop:
        middle = (start + stop) // 2
        mid_val = l[middle]
        if skey < mid_val:
            stop = middle
        else:
            start = middle
    return start if l[start] == skey else None

它将找到元素的最后一次出现等于skey。它还使用循环而不是递归，节省了执行函数所需的时间。

于 2013-05-07T23:19:32.003 回答