Code Kata 2 was harder than Kata 1. Dave is right, it’s hard to come up with five different ways to do something! However, I think I have five sufficiently different approaches to warrant a post. My code, in C#, is below the More tag.
Approach 1 is a simple for loop, starting at the bottom and working its way up. Approach 2 uses a different looping mechanism for variety, but it does its comparisons from both ends of the array, which is faster than Approach 1 for values towards the larger end of the array.
Approach 3 leverages the fact that in C#, the List object has a built-in IndexOf function, and frankly is the way I would normally implement it.
Approach 4 creates a Dictionary with index/value pairs (in other words, a hash table), then determines the result. Lookups after the hash is built should be very quick. However, for a large array, there’s a lot of overhead in creating the hash, and the hash would need to be maintained or recomputed if the array changes.
Approach 5 uses a bifurcation algorithm, basically implementing the Picard Iteration approach of successive approximations. By far, it was the hardest to write. It splits the array in half, checks which half the target value would be in, and repeats until it finds the target value or proves the target’s not in the array. For a small array like this, it’s overkill. For sparse lookups against a large array, it might even prove to be the fastest.
Approaches 2 and 5 were the last ones I came up with. I had to start questioning my assumptions, which is when I hit upon Approach 2. Approach 5 came to me in the shower while I was trying to apply my Math degree to the problem.
I can’t wait for Kata 3!
(I’m going to apologize for the code formatting in advance. I need to do some research about the hosting on Wordpress and what formatting is and isn’t allowed!)