CODEWITHSUNDEEP
rubyrecursionbinary-search
Ahmed Abdelaal
Ahmed Abdelaal

Reputation: 11

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

The error I keep getting is undefined method '>' for nil:NilClass

Upvotes: 1

Views: 1782

Answers (2)

kylezimmerdude
kylezimmerdude

Reputation: 1

If your arrays are sorted you could try something like this:

def search(arr, target)
 return nil if array.empty?
 
 mid_index = array.length / 2

 case target <=> array[mid_index]
 when -1
   search(array.take(mid_index), target)
 when 0
   mid_index
 when 1
   subs = search(array.drop(mid_index + 1), target)
   subs.nil? ? nil : (mid_index + 1) + subs
 end

end

Upvotes: 0

Cary Swoveland
Cary Swoveland

Reputation: 110675

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.

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.

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

Upvotes: 4

Related Questions