CodeKata – Binary search (chop) in Ruby
On Monday I was home with manflu and, facing a terrible lack of sympathy from a considerably pregnant wife, decided to start learning Ruby. I finished the Ruby Koans, a set of failing tests that walks you through aspects of the language. I now think that, after ‘Hello, World!’ and some basic algebra, TDD would be the best way to teach and learn programming in general.
Last night I found my way to CodeKata and started at Kata 2 for instant gratification. Kata 2 is to implement a binary search algorithm. My first try was just a linear search, which passed the tests, but wasn’t a binary search and for very big sets of test data is impractical. My second try is a recursive binary search:
def chop(needle, haystack)
# Special cases
return -1 if haystack.length == 0
if haystack.length == 1
return 0 if haystack[0] == needle
return -1
end
# find the middle element
mid = (haystack.length / 2).round
return mid if haystack[mid] == needle
if haystack[mid] > needle
#needle is in first half
return chop(needle, haystack[0..(mid-1)])
else
#needle is in second half
result = chop(needle, haystack[mid..haystack.length])
return result == -1 ? -1 : result + mid
end
end
My third try converts the recursive algo into an interative one:
def chop(needle, haystack)
depth = 0
while true
# Special cases
return -1 if haystack.length == 0
if haystack.length == 1
return depth if haystack[0] == needle
return -1
end
# find mid point
mid = (haystack.length / 2).round
return mid + depth if haystack[mid] == needle
# trim haystack based on which end to follow
if haystack[mid] > needle
#needle is in first half
haystack = haystack[0..(mid - 1)]
else
haystack = haystack[mid..haystack.length]
depth += mid
end
end
end
I found that while I was writing the different implementations I had a lot of love for these little chips of Ruby. Maybe it was the very expressive syntax (such as the Yoda-esque return X if condition) or just the nature of TDD itself. Either way I’m really enjoying Ruby.