ruby中的递归二进制搜索

Question

我一直在学习一些算法，但我找不到我的方法失败的原因。如果你能看一下这些代码，并阐明为什么会发生这种情况。我真的很感激。

我正在尝试编写一种方法，可以递归地二进制搜索数组，到目前为止，这是我的所有代码。

 def recursive_binary_search(arr, target)
   max_index = arr.length - 1
   mid_index = max_index / 2

   if arr[mid_index] > target
     new_arr = arr[0..(mid_index - 1)]
     recursive_binary_search(new_arr, target)
   elsif arr[mid_index] < target
     new_arr = arr[(mid_index + 1)..max_index]
     recursive_binary_search(new_arr, target)
   else
     return mid_index
   end
 end

我一直得到的错误是undefined method '>' for nil:NilClass

Answer 1

我无法重现OP报告的异常（因为产生异常的数据未在问题中给出），但主要问题是，因为max_index是从arr计算的，而arr是不断变小的，所以索引方法返回的方法与初始数组arr中的正确索引无关。

例如，假设arr = [1,2,3,4,5,6]和target = 6。在这种情况下，该方法将返回0（而不是5）作为目标元素的索引。这是因为arr将逐渐成为arr[3..6]，arr[4..6]，arr[5..6]和arr[6]，此时指数0将被退回。

以下是使用case语句编写方法的一种方法。该方法假设target是arr的元素，并且（根据二进制搜索的要求）arr的元素是有序的，从最小到最大。

def recursive_binary_search(arr, target, min_index=0, max_index=arr.size-1)
  mid_index = (min_index+max_index)/2
  case arr[mid_index] <=> target
  when  0  # arr[mid_index] == target
    mid_index
  when -1  # arr[mid_index] < target
    min_index = mid_index + 1
    recursive_binary_search(arr, target, min_index, max_index)
  when  1  # arr[mid_index] > target
    max_index = mid_index - 1
    recursive_binary_search(arr, target, min_index, max_index)
  end
end

arr = [1,2,3,4,5,6]

arr.each { |target| puts "#{target}: #{recursive_binary_search(arr, target)}" }
1: 0
2: 1
3: 2
4: 3
5: 4
6: 5