Tomblog

Another crappy blog no one reads

Binary search is broken!?

Two posts in one day? Unheard of. I must be sick…or dying? I’m not dying am I? Nope I just found something interesting that I should have found a long time ago!
I recently discovered the Google Research blog for myself, and on there they have a very interesting article about how pretty much every binary search ever written is broken. That’s right, one of the oldest, best tested algorithms in computer science has a bug that’s been laying around for decades just to be found. I really found this interesting. It’s a good example of how programmers can’t just assume code is bug free because they have tested a few cases, or literally billions of cases as with binary searches, bugs can be anywhere and we always have to be on the look out. This bug for example managed to avoid detection because it only occurs in very large arrays, and only when the value being searched for is somewhere on the far side of the upper half. For reference a large array in this case has somewhere in the range of a billion elements, and I’m sure you all write a couple of those a week. Only recently have computers been made to keep arrays this large and so only recently have arrays this large been made.

So just remember, never assume something works. Always be ready for those bugs that you just never dreamed could happen.

Tomasz Kolodziejczyk on November 4th, 2006 | Filed under Programming | Comment now »

Comments are closed.