调试二进制搜索

Question

下面是二进制搜索的实现，但它有问题。找到它并通过修改一行来修复它！

def binary_search(array, value, low, high):
    if high < low:
        return -1
    else:
        mid = (low + high)/2;
        if array[mid] > value:
            return binary_search(array, value, low, mid)
        elif array[mid] < value:
            return binary_search(array, value, mid+1, high)
        else:
            return mid
array = []
for i in xrange(10000):
    array.append(input())
for i in xrange(10000):
    value = input()
    answer = binary_search(array, value, 0, 9999)
    print("%d" % answer)

输入：

输入包含长度为10,000的排序数组，后跟10,000个查询。每个整数都以它自己的行给出（总共有20,000行）。

保证阵列中没有重复项。

输出：

对于每个查询值，输出一行包含单个整数的输出：与查询值匹配的索引，如果该值不在数组中，则返回-1。

---

我一直在尝试修复这段代码......我很确定if子句中的递归参数是错误的。不应该是：

if array[mid] > value:
            return binary_search(array, value, low, mid-1)

因为否则，如果数组中只有一个元素且元素>值，那么它将无限循环。但根据评估者的说法，结果代码仍然标记为错误的答案！

其他嫌疑人：

1. ';'在mid = (low + high)/2;虽然很刺耳，但它仍然编译得很好
2. (low + high)/2因为这是用python 2.7编写的，它相当于python 3中的(low + high)//2对吗？所以这里没问题......

所有的帮助表示赞赏。谢谢。

Answer 1

错误更进一步！

if high < low: #ERROR IS HERE
    return -1

如果value不在array中，这将导致无限递归。

推理：

high的价值绝不会低于low的价值。这是因为改变这些值的唯一方法是在递归调用中用mid替换它们。从mid=(high+low)//2，最终，他们将最终成为0或high。从(0+0)//2 == 0和(high+high)//2 == high开始，你最终会进行无限递归，直到堆栈爆炸。因此，你的修复看起来像一个简单的if high <= low:。

现在出现了一个新问题：

如果我们在high或0寻找价值怎么办？然后我们得到-1，因为值都是相同的。解决方案，使if语句更精确：

if high <= low and array[(low+high)//2] != value:

这段代码确保如果第一个条件成立，我们也确保中间元素实际上不是我们正在寻找的值。