错误在Python二进制搜索算法使用伪

-1

所以我想做一个递归二进制搜索算法和这里的时候是我使用的伪代码：错误在Python二进制搜索算法使用伪

BINARY-SEARCH(X, A, start, end) 
1 if start > end then 
2  return False 
3 middle = ((end - start)/2) + start 
4 if X = A[middle] then 
5  return True 
6 else if X < A[middle] then 
7  return BINARY-SEARCH(X, A, start, middle - 1) 
8 else 
9  return BINARY-SEARCH(X, A, middle + 1, end)

，这里是我的程序：

def binarySearchRec(value, list, start, end): 
    if start > end: 
     return False 
    middle = ((end - start)/2) + start 
    if value == list[middle]: 
     return True 
    elif value < list[middle]: 
     return binarySearchRec(value, list, start, middle - 1) 
    else: 
     return binarySearchRec(value, list, middle + 1, end)

，所以我不断收到的索引错误，每当我使用的值是不在列表中，但它工作正常，发现是在列表中的值，任何帮助将不胜感激

来源

2015-11-13 student

提示：Python的列表是零索引 – miraculixx

您能举例说明价值，列表，开始和结束该产品的例外情况吗？此外，您可能希望使用列表以外的变量名称，因为您正在跺跺内置类型。当我使用列表类型时，通常使用数据作为名称。 –

伪代码使用包含上限，这意味着“结束”是一个有效的索引。您必须将'len（a） - 1'作为'end'参数传递。 –

你使用' STA rt'和'结束'？我刚刚运行了你的函数，它对列表中不存在的值运行良好（返回False）。

来源

2015-11-13 21:50:39 Darya

因为答案已经送人了已经，我建议你尝试从另一个角度解决这个问题 - 通过测试它：

每当我使用的值不在列表中，但它工作正常查找用于在列表中

值有趣的代码不上阵列中的每一个失败数不。试用array = range(1,10,2)并搜索例如2，4，6，8 - 全部不在阵列中。它会工作。搜索10，它会失败。这暗示着极限检查可能是错误的，而不是像这样的实现。

任何帮助，将不胜感激

这里是一个测试你的功能，并很快看到什么号码是失败的方式：

from itertools import izip_longest as izipl 
def complement(a): 
    return list(set(range(min(a), max(a) + 10)) - set(a)) 
array = range(1,10,2) 
c_array = complement(array) 
start = 0 
end = len(array) # that's the culprit 
try: 
    for a,b in izipl(array, c_array): 
     if a: 
      assert binarySearchRec(a, array, start, end), "expected to find %s" % a 
     if b: 
      assert not binarySearchRec(b, array, start, end), "did not expect to find %s" % b 
     print "worked on", a, b 
except: 
    print "failed on", a, b 
else: 
    print "all is well" 
=> 
worked on 1 2 
worked on 3 4 
worked on 5 6 
worked on 7 8 
failed on 9 10

来源

2015-11-13 22:07:12 miraculixx

错误在Python二进制搜索算法使用伪

回答

相关问题