All entries for Wednesday 07 June 2006

June 07, 2006

(nearly) All binary searches are broken

Writing about web page http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

I love this. The standard algorithm for binary searches (and merge sorts, and other divide–and–conquer algorithms) is broken, and has been for approximately the last 60 years, and only in the last couple of years has anyone actually noticed.

Granted it's only broken for humungous arrays, but still, you'd think someone would have spotted it, given that it's taught on day one of pretty much every comp sci degree in the universe. Tells you something about the value of formal proofs I guess :–)


Most recent entries

Loading…

Search this blog

on twitter...


    Tags

    Not signed in
    Sign in

    Powered by BlogBuilder
    © MMXXI