mgroves

I’m still trudging through the CodeKata exercices.

Code Kata 2 is a challenge to implement the binary search algorithm. Binary search is an algorithm
that is used to search sorted arrays. The idea is very much like a “guess the number” game, where you
are pretty much guaranteed to win in a maximum of log₂(n) guesses (n being the size of the array). Compare this to a linear search,
where you start at the beginning of the array and search sequentially until you find the value. In the worst case,
you’d need to search every element (though binary search doesn’t work on an unsorted array).

The challenge is not to write a single binary search method, but 5 of them. The obvious first 2 are
recursive and iterative–everyone did those in those college. But what about another 3? This turned out
to be the most challenging part to me, and one that I did not ultimately succeed at.

My first method was recursive. With the method signature that’s given by the Code Kata test cases, this
was more challenging than I thought. Sure, I could basically make it a wrapper method, but I opted against
that. Instead, I had to learn to use Array.Copy. Note that this pretty much defeats the purpose of using
binary search instead of linear search, but it does confine the search to one method. In C++ or some other
unmanaged language, Array.Copy would not be necessary.

Secondly, I did the iterative approach, and this was much easier. There are 4 total cases and 3 comparisons
per iteration in this implementation. It felt suboptimal to me, and it turns out I was right.

Next, I hit a brick wall. What else can I really do? So I thought I would pull a Kirk and rig the
exam so that I could win. I simply made a chop() method that wraps around the built-in C# Array.BinarySearch
method. I had to kajagger the return value a bit to pass the test cases, but it works. Yeah it’s not
very interesting, but I didn’t know what else to do.

Finally, I broke down for the last two and just plain cheated. I looked up a couple of iterative implementations.
The first one did a single comparison per iteration,
and the second one is just a little nicer looking with max of 2 compares per iteration.

Here are the 3 Code Kata questions:

1. Keep notes on the errors. Did you learn from experience on one technique when coding
another?

Exactly as stated in the kata description, the errors I ran into were “fencepost” errors where it would pass most tests except maybe
one edge case. A quick adjustment of a -1 or +1 here and there made the fixes. It’s difficult sometimes when
using 0-based arrays to separate the maximum index and the length when juggling numbers in my head.

2. What can you say about the relative merits of the various techniques you’ve
chosen? Which is the most likely to make it in to production code? Which was the most
fun to write? Which was the hardest to get working? And for all these questions, ask yourself “why?”

My two methods are definitely smelly, and I wouldn’t want to use them in production. However, they all
passed test cases, so I could use them in a pinch. However, the only one I would want in production would be
the Kirk method: using the C# built-in search. Binary search has been written millions of times by thousands
of people smarter than me: there’s no sense in reinventing the wheel. That one was also the most fun to write,
because it was the quickest and easiest to write. The hardest to get working was the initial recursive method,
and this is only because I was committed to using one method with the given signature, and I was using a
managed language.

3. It’s fairly hard to come up with five unique approaches to a binary chop. How did
you go about coming up with approaches four and five? What techniques did you use to fire those “off the wall” neurons?

Heh, well, I really didn’t. I only came up with 3 totally on my own, and one of those didn’t really
count. Additionally, the two iterative methods that I stole were really just (better) variations of my own
lousy iterative method, so I’d be very much interested in seeing the code of someone who has written
5 unique approaches to binary search.

That’s the end of the second kata. It took me well over the standard week, but I actually only spent about 4-5
nights really cranking at this problem.

Here’s the code for Code Kata 2. Just rename the method you want to
run tests on to “chop”. I used C# with MbUnit.

One Response to “Code Kata 2 – Karate Chop”