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?]
