I’ll keep this short. I saw the first part of Kellan’s post today and decided to try my hand at it. I haven’t looked at his solution yet. Presented here is my attempt at a binary search in Ruby. I made two – one recursive for fun. I haven’t done any testing on this yet, so it might be broken. If it is… well being in with 90% of everyone else isn’t so bad is it?… is it? :)
One thing I was unclear on (going of the definition from the original post) was if the return should be the position in the array, a boolean or the searched-for element… I went with the last.
(if the embed doesn’t work, here they are on gist: http://gist.github.com/378840)
UPDATE: I tested the code out after posting it here (and have included my test suite in the embeded gist). I found a stupid typo bug in the non-recursive version:
- r = mid[mid] > needle ? 0...mid : mid+1..-1
+ r = valid_range[mid] > needle ? 0...mid : mid+1..-1
I’m going to try to think of a few more test cases before I call the matter closed. Kind of disappointed I made such a silly mistake :/
UPDATE 2: I added a pretty big test suite that someone wrote for this exercise. After fixing my very silly flub (in the first UPDATE), all the tests pass:
4 tests, 8206 assertions, 0 failures, 0 errors
I don’t know if I can give myself FULL credit, but the recursive one was right at first submission, so let’s say 95% ;)
UPDATE 3: GAHH! After benchmarking, I realized that this code isn’t O Log(N)… lame lame lame. I am not in the 10% at all ;). I’m pretty sure that Array#slice (which haystack[x...y] is a shortcut for) is O(N).
I’ve updated my gist with a better implementation (written after I looked at Kellan’s and others) along with benchmarks showing it’s O Log(N) (or thereabouts).