Python递归二分搜索函数不起作用,但无法看出原因。

huangapple go评论59阅读模式
英文:

Python recursive binary search function not working but cannot see why

问题

所有这些都是我第一次在这里发布。
我有一个递归二分搜索函数,应该可以工作。
但是没有。它有一个使用“或”逻辑运算符的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))

我预期的输出是4,但我一直得到-1的值返回。
这似乎是由这个if条件引起的

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

但是,我就是看不到这个if条件怎么会在函数开始时评估为true。我的函数可以看到A[L],它是31。它可以看到A[R],它是81(通过print语句验证),它也可以看到密钥。密钥是71。

那么,这个if是怎么评估为true的呢?正如我所说的,我确定这是一个小问题,但我看不到是什么问题。

英文:

all this is my first time posting here.
I've got a recursive binary search function which should work.
But isn't. It has an if condition that uses the 'or' logical operator
to test whether a key is outside the bounds of an input array.
That seems to be the source of the problem.
The if condition works outside my recursive function but doesn't seem to work inside it.
It's most likely a small issue but I cannot see what that issue could be

 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 &lt; A[L] or key &gt; A[R]:
     return -1
   M = (L + R) // 2
   if key &lt; A[M]:
     return recur_binary_search(A,L,M-1,key)
   elif key &gt; 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.

I expected an output of 4, but I keep getting a value of -1 returned.
This seems to be caused by this if condition

if key &lt; A[L] or key &gt; A[R]:
    return -1

But, I just cannot see how that if condition, could ever evaluate to true at the start of the function. My function can see A[L] which is 31. It can see A[R] which is 81 (verified via print statements) and it can see the key. The key is 71.

So, how is this if evaluating to true? As I said, I'm sure it is a small issue but I can't see what it is.

答案1

得分: 1

以下是翻译好的代码部分:

尝试这个

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

希望这对您有帮助。

英文:

try this:

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

  
def recurs_binary_search(A,L,R,key):
    if L&lt;=R:
        M=(L+R)//2
        if key&lt;A[M]:
            return recurs_binary_search(A,L,M-1,key)
        elif key&gt;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

答案2

得分: 0

你说你用 print 验证输入;那我建议在函数开始处添加一个 print 语句,以查看究竟发生了什么...

英文:

You said you used print to verify your inputs; then I'd recommend to add a print statement at the beginning of your function to see exactly what's happening ...

[...]
def recur_binary_search(A, L, R, key):
  print(f&quot;{L=}, {R=}, {key=}, {A[L]=}, {A[R]=}, {(L + R) // 2=}&quot;)
  if key &lt; A[L] or key &gt; A[R]:
    return -1
[...]

... gives ...

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

... so your A[M] never is 71; resp. you don't get the 4 that you expect because M never is 4.

That should be enough of a hint and for an answer to the "see why" of your question ... I don't want to spoil the solution - good luck and have fun!

答案3

得分: 0

你的逻辑在递归时似乎有点问题。当你发现key &lt; A[M]时,根据你提供的代码,应该返回recur_binary_search(A, L, M-1, key),因为你想要将值设置为middle-1。同样,如果你发现key &gt; A[M],你应该返回recur_binary_search(A,M-1,R,key),因为你想要将值设置为middle-1

你当前的算法只修改了值,这就是为什么你总是返回-1的原因。希望这提供了正确执行递归二分搜索的见解(同时仍然保持你发送的代码的一般形状)。如果需要进一步的澄清,请告诉我。

英文:

It seems that your logic when you recurse it a bit off. When you find that the key &lt; A[M], then (following the code you provided), you need to return recur_binary_search(A, L, M-1, key) because you want to set your right value to middle-1. Similarly, if you find that key &gt; A[M] you will want to return recur_binary_search(A,M-1,R,key) because you want to set your left value to middle-1.

Your general algorithm right now is only modifying your right value, and this is why you are always returning -1. Hopefully this provides insight into how to properly perform a recursive binary search (while still sticking to the general shape of the code you sent). Let me know if you need any further clarification.

答案4

得分: 0

嘿,大家,我找到问题了。谢谢你们的帮助。我在第二次递归调用时弄错了边界。(当我意识到时,我差点拍自己。哈哈)

    def recur_binary_search(A, L, R, key):
      if key < A[L] or key > A[R]:
        return -1
      else: 
       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, M+1, R, key) # 修复处
      else:
        return M
英文:

Hey y'all I found the problem. Thanks for helping. I messed up the boundaries on the second recursion call. (I almost slapped myself when I realized. lol)

def recur_binary_search(A, L, R, key):
  if key &lt; A[L] or key &gt; A[R]:
    return -1
  else: 
   M = (L + R) // 2
  if key &lt; A[M]:  
     return recur_binary_search(A,L,M-1,key)
  elif key &gt; A[M]:    
    return recur_binary_search(A,M+1,R,key) # the fix
  else:
    return M

答案5

得分: -1

返回的翻译部分如下:

返回-1而不是4的原因是因为or运算符用于布尔if语句。or运算符检查任何语句(key &lt; A[L]key &gt; A[R])是否为真。如果为真,则if语句将继续执行其后的代码(return -1)。如果为假,则if语句将break。如果您想要检查多个函数,则必须添加elif或另一个if

英文:

The reason why it is returning -1 instead of 4 is because the or operator is for boolean if statements. The or operator checks if any of the statements (key &lt; A[L] and key &gt; A[R]) are true. If it is true, than the if statement will go on to complete the code after it (return -1). If false, than the if statement will break. If you want to have more than 1 function checked, than you have to add a elif or another if.

huangapple
  • 本文由 发表于 2023年4月17日 05:20:30
  • 转载请务必保留本文链接:https://go.coder-hub.com/76030391.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定