我使用此二进制搜索功能获得更大数据集的索引错误 . 当我输入较小的数据集,即[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 .
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 回答
这个算法有几个问题 .
首先,如果您在列表中请求小于最小的项目(
skey < l[start]
),则它会循环 . 第二,当skey not in l[start:stop]
时,搜索会随着索引越界而下降 .对于未在列表中显示元素的情况,您没有适当的行为 . 例如,如果找不到元素,则可以返回
None
. 您的代码可以通过以下方式修复:它会发现元素的最后一次出现等于
skey
. 它还使用循环而不是递归,节省了执行函数所需的时间 .你永远不会检查
stop
是否小于start
. 您的递归调用很容易创建该条件 .