Binary Chop

Now that I have a laptop from work I don't need to exile myself the spare bedroom in order to try things out on the computer. Thanks to wi-fi I have ruby and vim, which means I can look at kata again.

Actually, I wanted to try out binary chop, as it's something I can use on a work project. Stupidly, I tried first to write the code cold. That didn't work. Not only did I have the fencepost errors and the endless loops — the code was getting uglier as I kept thinking of special cases. It probably didn't help that my Ruby is rusty from lack of use. I've been spoiled by IDEs and auto-completion: one almost forgets what it's like to get compile errors.

So I resorted to pen and paper. A funny thing happened: all Dave's tests passed at once. The code was easier to read and more coherent. Binary chop is about the simplest problem I know for which it's really worth taking a break from the keyboard.

Interesting to compare with other people's work. Jim Weirich did a version three years ago. Here's mine:

module BinChopper

    def chop(n, a)
        lo = 0
        hi = a.length - 1
        while lo <= hi
            mid = (lo + hi) / 2
            if a[mid] == n
                return mid
            elsif (a[mid] > n)
                hi = mid - 1
            elsif (a[mid] < n)
                lo = mid + 1
            end
        end
        return -1
    end

end

Originally, I was using single letter variable names but I like Jim's short but meaningful names better. I thought of the invariant a little differently: I decided the loop would terminate after the high and low markers went past each other. (By the way I think his calculation of the midpoint is buggy. I should lay off the crack pipe. His calculation is obviously correct and I'm stealing it.)

Now of course coming up with one implementation of binary chop is straightforward. I'll have to see how motivated I am to find four more ways to do it.