Python 递归二进制搜索功能不起作用但看不出原因

Question

这都是我第一次在这里发帖。 我有一个应该工作的递归二进制搜索功能。 但不是。它有一个使用“或”逻辑运算符的 if 条件 测试键是否在输入数组的边界之外。 这似乎是问题的根源。 if 条件在我的递归函数之外起作用，但在它内部似乎不起作用。 这很可能是一个小问题，但我看不出那个问题可能是什么

 A = [31,48,59,62,71,75,81]
 L=0
 R=len(A)-1
 key = 71

 def recur_binary_search(A, L, R, key):
   if key < A[L] or key > A[R]:
     return -1
   M = (L + R) // 2
   if key < A[M]:
     return recur_binary_search(A,L,M-1,key)
   elif key > A[M]:
     return recur_binary_search(A,L,M+1,key)
   else:
     return M

 print( recur_binary_search(A, L, R, key))
 # my code keeps returning -1 rather than the correct value, 4.

我期望输出为 4，但我一直得到 -1 的返回值。 这个好像是这个if条件引起的

if key < A[L] or key > A[R]:
    return -1

但是，我只是看不出

if

条件如何在函数开始时评估为真。我的函数可以看到

A[L]

是 31。它可以看到

A[R]

是 81（通过打印语句验证）并且它可以看到密钥。关键是71.

那么，如果评估为真，这又如何呢？正如我所说，我确定这是一个小问题，但我看不出它是什么。

Answer 1

你说你使用 print 来验证你的输入；那么我建议在函数的开头添加一个 print 语句，以准确查看发生了什么......

[...]
def recur_binary_search(A, L, R, key):
  print(f"{L=}, {R=}, {key=}, {A[L]=}, {A[R]=}, {(L + R) // 2=}")
  if key < A[L] or key > A[R]:
    return -1
[...]

...给...

L=0, R=6, key=71, A[L]=31, A[R]=81, (L + R) // 2=3
L=0, R=4, key=71, A[L]=31, A[R]=71, (L + R) // 2=2
L=0, R=3, key=71, A[L]=31, A[R]=62, (L + R) // 2=1
-1

... 所以你的

A[M]

永远不会是 71；分别你没有得到你期望的 4 因为

M

永远不是 4.

这应该足够提示和“看看为什么”......我不想破坏解决方案 - 祝你好运，玩得开心！

Answer 2

试试这个：

A = [31,48,59,62,71,75,81]
key = 71

  
def recurs_binary_search(A,L,R,key):
    if L<=R:
        M=(L+R)//2
        if key<A[M]:
            return recurs_binary_search(A,L,M-1,key)
        elif key>A[M]:
            return recurs_binary_search(A,M+1,R,key)
        else:
            return M
    else:
        return -1
 

recurs_binary_search(A,0,len(A)-1,key)
4

Answer 3

它返回 -1 而不是 4 的原因是因为

or

运算符用于布尔

if

语句。

or

运算符检查是否有任何陈述（

key < A[L]

和

key > A[R]

）为真。如果为真，则

if

语句将继续完成其后的代码 (

return -1

)。如果为假，则

if

语句将

break

。如果您想检查超过 1 个功能，则必须添加一个

elif

或另一个

if

.