Refactoring binary search algorithm in Ruby

Question

I wrote the binary search algorithm with Ruby, the code is below. The question is if there's any way to make it look cleaner?

def binary_search(sample_array, x, l, r)
 mid = (l + r)/2
 return -1 if r < l
 return binary_search(sample_array, x, l, mid-1) if (sample_array[mid] > x)
 return binary_search(sample_array, x, mid+1, r) if (sample_array[mid] < x)
 return mid if (sample_array[mid] == x)
end
result = binary_search(sample_array, x, l, r)
puts "#{result}"

It seems to me that returns can be minimised or even some more Ruby idioms added. Tried to use lambda, but smth went wrong.

• Steve Jessop: If nothing else, you can make it tail-recursive by conditionally assigning a new value to l or r (or returning) according to the comparisons between sample_array[mid] and x.

Answer 1

• Rather than defining it at the top level, why don't you make it a new method on Array?
• Taking l and r makes recursive calls possible, but would be annoying for the end user who always has to pass 0 and array.length-1. You should either make those arguments optional, or don't use recursion, or use a private helper method for the recursion.
• Someone suggested you could make it tail-recursive, but I don't think any Ruby implementation I know of can optimize tail recursion, so I'm not sure what the point of that would be. Method calls are expensive in Ruby, so if you are after performance, I think a while loop would be more appropriate.
• You could consider calling <=> once and switching on the return value using case. I'm not sure if you would like the way this reads better or not. If performance is important, definitely try it and benchmark both ways.
• If you do want to use if statements, the 3rd if is redundant.
• You are using the type of binary search which has 3 different branches (depending on whether the value at the probed index is >, <, or == to the value you are searching for). There is another to write a binary search which only uses a single if-else, which is more concise, generally faster, and which is guaranteed to return the first matching element in the array (if there are duplicates).

• mac-r: Thanks for great pieces of advice! A lot of things to think on.