这个二分查找实现在Ruby中为什么会导致栈溢出,而在Java中却不会?

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

Why does this binary search implementation cause stack overflow in Ruby but not Java?

问题

在Ruby中,当目标元素x位于已排序数组的右半部分时,会发生堆栈溢出错误,错误消息为"SystemStackError (stack level too deep)"。而在Java中没有出现这个问题。这个问题的原因在于Ruby和Java在递归调用方面有不同的行为。

在Ruby中,递归的深度有限制,当递归调用的层数过多时,会触发堆栈溢出错误。这是因为Ruby默认情况下对递归的深度设置了限制,以防止无限递归导致程序崩溃。在你的Ruby代码中,递归调用的深度可能超出了Ruby的默认限制,导致堆栈溢出错误。

而在Java中,堆栈的大小通常更大,因此可以容纳更深层次的递归调用。这就是为什么在Java中没有出现相同的堆栈溢出问题的原因。

要解决这个问题,你可以考虑优化Ruby代码,以减少递归调用的深度,或者使用迭代而不是递归来实现二分查找算法,以避免堆栈溢出错误。

英文:

Ruby

def binary_search(arr, l, r, x) 
  if r >= 1 then
    mid = l + (r - 1) / 2

    if arr[mid] == x then
      return mid
    end

    if arr[mid] > x then
      return binary_search(arr, l, mid - 1, x)
    end
    return binary_search(arr, mid + 1, r, x)
  end

  return -1
end

Java

int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 

        // If the element is present at the 
        // middle itself 
        if (arr[mid] == x) 
            return mid; 

        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 

        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 

    // We reach here when element is not present 
    // in array 
    return -1; 
} 

When x (the target element) is in the right half of a sorted array, a stack overflow occurs and I get this error in Ruby

SystemStackError (stack level too deep)

why does this happen in ruby and not in java? I'm running the program in irb. the java implementation came straight from here https://www.geeksforgeeks.org/binary-search/ .

答案1

得分: 3

以下是代码的翻译部分:

def binary_search(arr, l, r, x) 
  return -1 unless r >= 1

  mid = l + (r - 1) / 2

  case arr[mid] <=> x
  when  0 then mid
  when -1 then binary_search(arr, mid + 1, r, x)
  when  1 then binary_search(arr, l, mid - 1, x)
  end
end

首先,让我们重构您的代码,使其更清晰一些。请注意:在此代码中,几乎没有行为更改,主要是重新格式化并进行了一些重构。

您的二分搜索存在两个主要问题。

首先是您对“未找到元素”的终止条件。您的二分搜索方式是,根据数组中所需元素的位置,要么将左边的“栅栏”向右移动,要么将右边的“栅栏”向左移动。这样,搜索区域会变得越来越小。

现在,当这两个“栅栏”相遇(甚至彼此超越)时,就没有更多的“搜索区域”了,这意味着未找到元素。然而,您没有检查这两个“栅栏”是否相遇(l == r)甚至超越了对方(l >= r),而是检查r是否与原始数组的左边界相遇(r == 1)。

这意味着您将有更多无用的递归,直到最终发现元素未找到。

实际上,情况并不那么简单,因为当lr相互越过时,您的中点计算也是错误的,因为现在突然r小于l,或者换句话说,右栅栏在左栅栏的左侧!

嗯...除非您的中点计算无论如何都是错误的。例如,如果l = 10r = 12,两者之间的中点显然是mid = 11,但根据您的公式,它是:

10 + (12 - 1) / 2
10 + (  11  ) / 2
10 + 5
15

哎呀!左和右之间的中间点实际上远远在右边!这意味着,根据数组中搜索值的位置,您实际上使搜索区域变得更大而不是更小:您将r向右移动,以便再次搜索已经搜索过的数组的一部分!这再次意味着,与您的Java版本相比,您的Ruby版本需要更多的递归。

当前lr之间的距离的公式是r - l。现在我们需要这个距离的一半,即(r - l) / 2。如果我们要找到lr之间的中点,我们需要从lr的一半距离,因此我们需要将上述距离加到l上:l + (r - l) / 2

这是修复后的代码:

def binary_search(arr, l, r, x) 
  return -1 if r < l

  mid = l + (r - l) / 2

  case arr[mid] <=> x
  when  0 then mid
  when -1 then binary_search(arr, mid + 1, r, x)
  when  1 then binary_search(arr, l, mid - 1, x)
  end
end
英文:

First, let's refactor your code to be a little bit clearer. Note: there are zero behavior changes in this code, it is mostly re-formatting with a little bit of refactoring.

def binary_search(arr, l, r, x) 
  return -1 unless r &gt;= 1

  mid = l + (r - 1) / 2

  case arr[mid] &lt;=&gt; x
  when  0 then mid
  when -1 then binary_search(arr, mid + 1, r, x)
  when  1 then binary_search(arr, l, mid - 1, x)
  end
end

There are two main problems with your binary search.

First is your termination condition for "element not found". The way your binary search works is that it moves either the left "fence" to the right or the right "fence" to the left, depending on where the desired element must be in the array. That way, the search area gets smaller and smaller.

Now, when the two "fences" meet (or they even pass by each other), there is no more "search area", which means that the element wasn't found. However, you are not checking whether the two "fences" meet (l == r) or even overtake each other (l &gt;= r), you are checking whether r meets the left boundary of the original array (r == 1).

This means you will have many, many more useless recursions until you finally give up when the element is not found.

Actually, it is not even that simple, because when l and r pass by each other, your midpoint calculation is also wrong, because now all of a sudden r is smaller than l, or in other words, the right fence is on the left side of the left fence!

Well … except that your midpoint calculation is broken anyway. For example, if l = 10 and r = 12, the midpoint between the two is obviously mid = 11, but according to your formula, it is:

10 + (12 - 1) / 2
10 + (  11  ) / 2
10 + 5
15

Oops! The middle between left and right is actually way to the right of right! This means that, depending on where in the array, your search value is, you are actually making the search area bigger instead of smaller: you are moving r back to the right, so that you are searching a part of the array again that you have already searched! Again, this means that you need many more recursions in your Ruby version than in your Java version.

The formula for the current distance between l and r is r - l. Now we need half of that distance, which is (r - l) / 2. If we want to find the point halfway between l and r, we need to walk half the distance from l to r, so we need to add the above distance to l: l + (r - l) / 2.

Here's what the fixed code looks like:

def binary_search(arr, l, r, x) 
  return -1 if r &lt; l

  mid = l + (r - l) / 2

  case arr[mid] &lt;=&gt; x
  when  0 then mid
  when -1 then binary_search(arr, mid + 1, r, x)
  when  1 then binary_search(arr, l, mid - 1, x)
  end
end

huangapple
  • 本文由 发表于 2020年7月30日 23:16:55
  • 转载请务必保留本文链接:https://go.coder-hub.com/63176262.html
匿名

发表评论

匿名网友

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

确定