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

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/ .

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 >= 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

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 >= 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 < 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