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

Question

我是算法方面的新手。我最近开始研究二进制搜索，并尝试自己实现它。任务很简单：我们有一个整数数组a和一个整数x。如果a包含x，则结果应为其索引，否则函数应返回-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

但该代码在CCD_ 6和CCD_。我想，我有不正确的循环条件(可能，应该是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都具有与之前相同的值，这将产生一个无休止的循环。

阿肖克的答案是一个很好的解决方案。但我认为对固定代码进行一些桌面检查并看看有什么改进是有教育意义的

当l + 1 = r。然后m将始终评估为l，a[l] < x，并且l再次设置为m，这不会改变情况。

在一段较大的代码中，创建一个表是有意义的，该表包含每个要监视的变量的一列，以及写下计算代码行的一列。专栏发表评论也无妨。

Answer 2

正如Mani提到的，A[m]==x时您没有考虑。包括该案例(此时您已找到a，因此只需返回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