Binary Search y’all.

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).

One thought on “Binary Search y’all.”

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>