How to control nil in this binary_search algorithm

Question

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

It's not necessary, or desirable, for you to apologize for a lack of experience on SO. We want to see certain things in a question, and if you've done your research and tried, tried, tried and still can't figure it and follow the guides for "How to Ask" and the linked pages then we'll take it from there. I think you did pretty good, minus the apologies. — the Tin Man
– the Tin Man, Commented Nov 24, 2019 at 22:22

the Tin Man · Accepted Answer · 2019-11-24 22:19:34Z

1

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.

edited Nov 24, 2019 at 22:19

the Tin Man

161k44 gold badges222 silver badges308 bronze badges

answered Nov 24, 2019 at 20:24

Gene

47.1k4 gold badges64 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

steenslag Over a year ago

Also note that Arrays already have a bsearch method.

Gene Over a year ago

@steenslag OP did say he was trying to work through the algorithms in a book.

steenslag Over a year ago

sure! But for future readers it can be useful to know there is an existing method.

Collectives™ on Stack Overflow

How to control nil in this binary_search algorithm

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related