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 :–)


- 5 comments by 4 or more people Not publicly viewable

  1. Mathew Mannion

    I didn't learn it until the middle of my second term actually… And I still can't remember it.

    But then, I don't have to remember anything anymore, that's what Wikipedia's for…

    07 Jun 2006, 11:55

  2. Matthew Jones

    I learnt it at A–level. Wish I'd known it didn't work then; it would've been cool to pwn the teacher.

    It makes you wonder how many of the other 'standard' algorithms are borked as well. I'd like to think it's a few just to prove no–ones perfect.

    07 Jun 2006, 12:07

  3. Chris May

    Second term? bah. Don't know what the world's coming to these days. mutter, grumble, etc. etc.

    Actually, AFAICR I've never ever had to actually write one in the real world. That's what class libraries are for :–)

    07 Jun 2006, 12:07

  4. Steve Rumsby

    Actually, AFAICR I've never ever had to actually write one in the real world. That's what class libraries are for :–)

    Bah! You youngsters have it so easy. Everybody else does all the hard work for you. Now when I were a lad… :–)

    07 Jun 2006, 12:41

  5. Matthew Buckett

    Shows that unit testing at the extremes is often worth it, although even if you attempted to sort an array of bytes (smallest datatype that Arrays.binarySearch() supports) of the maximum size:

    byte bigArray[] = new byte[Integer.MAX_VALUE];
    then unless your machine can run process larger than 2Gb it's going to fail ( 8*(2^31–1) ).

    07 Jun 2006, 12:59


Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.

Most recent entries

Loading…

Search this blog

on twitter...


    Tags

    Not signed in
    Sign in

    Powered by BlogBuilder
    © MMXXI