调试二进制搜索

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)

否则，如果数组中只有一个元素，并且元素 > 值，则会无限循环。但是根据评估者，结果代码仍然被标记为错误答案！

其他嫌疑人：

';'在 mid = (low + high)/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:

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

调试二进制搜索

Debugging Binary Search

python

algorithm

binary-search

python-2.7