python - 调试二进制搜索

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. (低 + 高)/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:

此代码确保如果第一个条件成立，我们还确保中间元素实际上不是我们要查找的值。