Last night I attended the 5th Brighton Coding Dojo. The task: to implement binary search in 5 different ways (source).
Only four people turned up (myself included), but we still managed to make a good go of things. Richard Dallaway had prepared an interface, a unit test and a sample implementation (using Arrays.binarySearch)). This was an enormous head start, allowing us to really focus on the problem at hand, as well as check that we’d actually implemented it correctly.
Binary search is an algorithm which is readily understood. Yet it has a large number of corner cases when it comes to actually implementing it. I believe that our basic maths skills were all found to be lacking. I think the only problem we didn’t come across was the infamous google’s large arrays problem.
When we’d finished, we’d managed to implement four different variations:
- A SimpleSearch, which in all honesty probably doesn’t count, as it was pretty much a linear scan through the array.
- A RecursiveSearch, which was far too much hard work for what it was doing.
- A RandomSearch, which worked surprisingly well, once we’d upped the maximum number of attempts to something suitable large.
- A GuessingSearch, which tried to spot when we were looking at a a value near the beginning or end of the array and optimise accordingly.
Overall, really good fun. Especially familiarizing yourself with an area of programming that you probably don’t use all that often. Once again, thanks to Joh for organising.
When I got home, I started on an alternate approach: converting the list to a string of numbers and counting the number of commas before and after. I haven’t finished this yet, and I don’t expect it to be performant, but hey’ it’s another approach!
Jabbering Giraffe 