Tuesday, September 02, 2008

Google Research:All Binary Searches and Mergesorts are Broke

I remember vividly Jon Bentley's first Algorithms lecture at CMU, where he asked all of us to write a binary search, and then dissected one of our implementations in front of the class.Of course it was broken, as were most of our implementations.Fast forward to 2006. I was shocked to learn that the binary search program that Bentley proved correct

read more | digg story