红宝石中的递归二进制搜索 [英] recursive binary search in ruby

问题描述

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

I've been learning some algorithms and I can't find the reason why my method is failing. if you could look at the code and shed some light as to why that is happening. I would truly appreciate it.

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

I'm trying to write a method that would binary search an array recursively and so far that is all my code.

 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'>'对于nil:NilClass

推荐答案

我无法重现OP报告的异常(因为没有在问题中给出产生异常的数据)，但是主要的问题是，因为 max_index 是根据 arr 计算的，并且 arr 不断变小，所以该方法返回的索引将与正确的索引无关在初始数组 arr 中.

I was unable to reproduce the exception reported by the OP (as the data that produced the exception was not given in the question), but the main problem is that, because max_index is computed from arr, and arr is constantly getting smaller, the index returned by the method will have no relation to the correct index in the initial array 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 .

Suppose, for example, that arr = [1,2,3,4,5,6] and target = 6. In this case the method will return 0 (rather than 5) as the index of the target element. That's because arr will progressively become arr[3..6], arr[4..6], arr[5..6] and arr[6], at which point index 0 will be returned.

这是使用 case 语句编写方法的一种方式.该方法假定 target 是 arr 的元素，并且(按二进制搜索的要求) arr 的元素是有序的，从小到大.

Here is one way the method could be written, using a case statement. The method assumes that target is an element of arr and (as required by binary searches) the elements of arr are ordered, smallest to largest.

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

这篇关于红宝石中的递归二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！