Rosio Pavoris a blog

I was browsing Reddit (with the quality of Slashdot’s editing going from utterly crap to considerably worse, and the discussion going from merely ignorantly libertarian to frothing-at-the-mouth ultra-conservatism, I need a new place to get my tech news from, so I’ve been trying a few other websites), and I came across this article on the “eight ball problem”.
If you’re averse to clicking links, the idea is that you’re given eight balls, one of which is slightly heavier than the others, and a set of scales. Your task is to find the heavier ball in as few weighings as possible.

I’ve been told it’s a popular job interview question, and the author of the article is probably right in saying that most computer science types would naturally try a binary search, which would get you the heavier ball in three weighings.
He then goes on to describe an algorithm that does it in two weighings: first you weigh balls 1 through 3 against 4 though 6. If both sets weigh the same, the heavier ball is either 7 or 8, and you just weigh those against each other. If not, take the set of three that was the heaviest and weigh the first ball against the second. If they weigh the same, the heavier ball is the third. If not, you have found the heavier ball.

This is indeed faster for eight balls, but is it faster in all situations, and how much?

The algorithm can be generalised as follows:

1. If you have one ball, you are done. It is the heavier. Otherwise:
2. Make two sets of n balls where n is the number of balls divided by three, rounded up. The third set, which may be empty, is the remainder of the balls.
3. Weigh the first set against the second.
4. If they weigh the same amount, your new set of balls is the third set. Otherwise, the new set is the heavier of the two sets. Discard the other balls.
5. Go back to step 1.

The astute among you may have noticed that while the binary search algorithm will always finish in the same time, this isn’t always true for this other algorithm; its best- and worst-case performance times differ for sets of balls that aren’t neatly divisible by 3 all the way down.
It’s not going to be a huge difference, especially for small amounts of balls, but it’s good to note.

The binary search will always take log₂(n) weighings to find the heavier ball, where n is the number of balls. It’s not immediately obvious how many the new algorithm will take, so let’s just write a program simulating it and run it a bunch of times.
While this seems an obvious place to use a functional language, I’m sorry to admit that I don’t yet feel comfortable with Haskell, and Scheme isn’t very legible, so I did it in Java.¹
That program outputs data in a gnuplot-friendly format, so let’s use it (gnuplot doesn’t like logarithms in base 2, but you’ll remember from your high school maths that log(n) / log(2) is equivalent):

We noted earlier that the second algorithm won’t always take the same amount of time, so the plotted line is the average time it will take. If you want to see the best- and worst-case performances plotted as well, you can do so yourself. The output data is here.

So yes, it does look like this algorithm is always faster, though binary search should really be fast enough for most purposes, and it’s somewhat easier to implement.
For 10,000 balls, this algorithm takes 8.84 weighings on average (and 9 in the worst case), while a binary search takes 14. For a million, it takes about 12.95 (13 in the worst case), and a binary search takes 20.
Unless someone is killing one of your loved ones for each weighing, I wouldn’t bother.

¹ Even as Java goes this is slower than it could be. For legibility’s sake I’m using Ball objects of my own making when I could be using ints or even booleans to represent the balls, for instance, and a getWeight() method call rather than a not-that-much-longer inline calculation. I invite you to write your own, better code in your favorite language.
Update: Like Python, for example. That was surprisingly painless, especially considering that it’s the first thing I’ve ever written in Python. It took maybe a third of the time it took me to write the Java version to write, and it’s not even that much slower, even though it’s an interpreted language.