Peter Luschny writes in with yet another way to break my supposedly bullet-proof binary search algorithm. You’re searching an array of whatevers; well suppose that array is declared:
Whatever[] w = new Whatever[Integer.MAX_VALUE * 2];
I checked, and Java will compile that happily. Binary search fall down go boom. Sigh. So, if you think you might have more than a couple billion elements in your array, you’d be better off declaring all your indexing variables as long. (Which should be free on a 64-bit computer, right?) I’ll go update the binary-search article to add this caution. [Update: Maybe not. Greg Thompson and A. Sundararajan both point out that the Java Language Definition requires array indices to be integers, not longs. So I wonder why this compiles?]


author · Dad · software · colophon · rights
picture of the day
June 15, 2006
· Technology (85 fragments)
· · Coding (98 more)

By

I am an employee of Amazon.com, but the opinions expressed here are my own, and no other party necessarily agrees with them.

A full disclosure of my professional interests is on the author page.