为何Ruby二分查找实现会栈溢出而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;
}

你遇到的问题是：当目标元素x在有序数组右半部分时，Ruby代码在irb中运行会触发SystemStackError（栈溢出），但Java版本却完全正常。核心原因其实是Ruby代码里的两个逻辑错误导致了无限递归，和语言本身的栈深度关系不大：

1. 致命错误：中间位置mid的计算逻辑写错了 #

仔细对比两段代码的mid计算：

• Java的计算是正确的：mid = l + (r - l) / 2，这个公式能精准算出当前搜索区间[l, r]的中间位置，保证每次递归都能把搜索区间缩小一半，最终会收敛到终止条件。
• Ruby的计算却出现了低级错误：mid = l + (r - 1) / 2，这里把本该是r - l的地方写成了r - 1，直接导致中间位置的计算严重偏移。

举个实际例子，假设我们在数组[1,3,5,7,9]中查找9（右半部分的元素）：

• 初始调用：l=0, r=4，Ruby计算mid为0 + (4-1)/2 = 1，对应元素3，比9小，所以递归调用binary_search(arr, 2, 4, 9)。
• 第二次调用：l=2, r=4，mid计算为2 + (4-1)/2 = 3，对应元素7，还是比9小，递归调用binary_search(arr,4,4,9)。
• 第三次调用：l=4, r=4，mid计算为4 + (4-1)/2 = 5，这时候arr[5]已经超出数组边界（Ruby访问越界索引会返回nil），但代码判断r >=1（4>=1成立），继续执行：因为nil和9不相等，且nil > 9为false，所以会递归调用binary_search(arr,6,4,9)。
• 此时l=6, r=4，但代码的终止条件是r >=1，4>=1依然成立，递归会无限循环下去，每次调用都会生成新的栈帧，直到栈被撑爆，触发SystemStackError。

而Java版本的终止条件是r >= l，当l=6, r=4时，这个条件不成立，直接返回-1，递归正常终止。

2. 第二个错误：递归终止条件逻辑错误 #

Ruby代码里的终止条件写成了if r >= 1，这完全不符合二分查找的逻辑！正确的终止条件应该和Java一致：当左边界l大于右边界r时，说明搜索区间不存在，应该返回-1。r >=1的判断完全不合理，哪怕l已经远大于r，只要r大于等于1，递归就会继续执行，这也是无限递归的推手之一。

修正后的Ruby代码 #

只要把这两个错误修正，Ruby版本就会和Java一样正常工作，不会再出现栈溢出：

def binary_search(arr, l, r, x)
  if r >= l then
    mid = l + (r - l) / 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

内容的提问来源于stack exchange，提问作者math4545454