CODEWITHSUNDEEP
rubyalgorithmsearchbinary
f1729
f1729

Reputation: 13

How to control nil in this binary_search algorithm

I'm reading the Grokking Algorithms book, and I'm implementing the binary_search function but recursively, so, my algorithm works if the item is in the list.

Any suggestions on how to control when I have a nil?

def recursive_binary_search(list, item)
  if list.length == 0
    return nil
  elsif list.length == 1
    print list
    if list.first == item
      return 0
    else
      return nil
    end
  else
    low = 0
    high = list.length - 1
    mid = (low + Float(high - low)/2).round()
    guess = list[mid]

    if guess == item
      return mid
    elsif guess < item
      return mid + 1 + recursive_binary_search(list[mid+1..-1], item)
    else
      return recursive_binary_search(list[0..mid-1], item)
    end
  end
end

my_list = [1, 3, 5, 7, 9]

puts recursive_binary_search(my_list, 100) # => nil

Upvotes: 0

Views: 63

Answers (1)

Gene
Gene

Reputation: 46960

You're close.

First, the gyration to compute the middle index isn't needed. Just say

mid = list.length / 2

Integer division in Ruby truncates, so the result is always the integer you want.

The second recursive call is a problem. It can return nil. So you need to save the return value and only do the index arithmetic if it's not nil.

Finally note that since Ruby naturally returns the last value it computes, all your returns can be omitted. This makes the function read as an expression, which is more Ruby-like.

def recursive_binary_search(list, item)
  if list.length == 0
    nil
  elsif list.length == 1
    if list.first == item
      0
    else
      nil
    end
  else
    mid = list.length / 2
    guess = list[mid]
    if guess == item
      mid
    elsif guess < item
      result = recursive_binary_search(list[mid+1..-1], item)
      if result.nil?
        nil
      else
        1 + result + mid
      end
    else
      recursive_binary_search(list[0..mid-1], item)
    end
  end
end

The only case where return is needed is to exit a function immediately when more computation is possible.

Finally note that though this is great for learning, in a real implementation you'd avoid tail recursion in Ruby because, unlike some other languages, Ruby is not guaranteed to optimize it as a loop. Since binary search can be very naturally implemented without recursive calls, you'd want to do that instead.

Upvotes: 1

Related Questions