二进制搜索算法中的无限循环

Question

我是算法新手。我最近开始研究二进制搜索并尝试自己实现它。任务很简单：我们有一个整数数组 a 和一个整数 x。如果 a 包含 x 结果应该是它的索引，否则函数应该 return -1.

这是我写的代码：

def binary_search(a, x):
    l = 0
    r = len(a)
    while r - l > 0:
        m = (l + r) // 2
        if a[m] < x:
            l = m
        else:
            r = m
    if a[l] == x:
        return l
    return -1

但是此代码在 a = [1, 2] 和 x = 2 上陷入无限循环。我想，我的循环条件不正确（可能应该是 r - l >= 0），但这个解决方案没有帮助。我哪里错了？

Answer 1

让我检查一下桌面。我假设 a = [1, 2] 并且我们正在搜索 2

所以我们从

开始

l = 0
r = 2

从r - l = 2 > 0开始，我们进入while循环。

m = (l + r) / 2 = (0 + 2) / 2 = 1
a[m] = a[1] = 2 == x  (hence not less than x)
r = m = 1 (and l remains the same)

现在r - l = 1 - 0 = 1 > 0，所以我们继续

m = (l + r) / 2 = (0 + 1) / 2 = 0
a[m] = a[0] = 1 < x
l = m = 0 (and r remains the same)

在这次迭代之后，r 和 l 都具有与之前相同的值，然后产生无限循环。

Ashok 的回答是一个很好的解决方法。但我认为对固定代码进行一些案头检查并看看有什么改进它会很有教育意义。

当l + 1 = r 时，问题基本上就出现了。然后 m 将始终评估为 l，a[l] < x 并且 l 再次设置为 m，这不会改变情况。

在较大的代码段中，制作一个 table 是有意义的，其中包含一个用于观察每个变量的列和一个用于记下已评估代码行的列。备注栏也无妨。

Answer 2

正如 Mani 提到的，您没有考虑 A[m]==x。包括那种情况（那时你已经找到 a 所以只是 return m），一旦你有了这种情况，当我们仍然低于 x 时我们可以让 l=m+1 .像这样：

def binary_search(a, x):
    l = 0
    r = len(a)
    while r - l > 0:
        m = (l + r) // 2
        if a[m] < x:
            l = m + 1
        elif a[m]==x:
            return m
        else:
            r = m
    if l<len(a) and a[l] == x:
        return l
    return -1

二进制搜索算法中的无限循环

Infinite loop in binary search algorithm

python

algorithm

binary-search