首页 文章

二进制搜索算法的实现

提问于
浏览
0

我使用此二进制搜索功能获得更大数据集的索引错误 . 当我输入较小的数据集,即[1,2,3,4,5]搜索5.算法按预期运行 . 但是,当我使用下面的文本时,使用参数的空列表调用字符串对象的split方法(delimeter char是'')并将字符串分解为列表值,其中每个元素都是一个字符串,并搜索单词' culpa'我最终得到以下错误:

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 repreptderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur . Excepteur sint occaecat cupidatat non proident,sunt in culpa qui officia deserunt mollit anim id est laborum .

代码: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))

2 回答

  • 0

    这个算法有几个问题 .

    首先,如果您在列表中请求小于最小的项目( skey < l[start] ),则它会循环 . 第二,当 skey not in l[start:stop] 时,搜索会随着索引越界而下降 .

    对于未在列表中显示元素的情况,您没有适当的行为 . 例如,如果找不到元素,则可以返回 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 . 它还使用循环而不是递归,节省了执行函数所需的时间 .

  • 0

    你永远不会检查 stop 是否小于 start . 您的递归调用很容易创建该条件 .

相关问题