3 ms·

The author is claiming that nearly all binary search implementations are wrong under those specific conditions, not that binary search implementations are wrong

• tbrownaw 15y ago
  ...bah. I keep forgetting that 64-bit C/C++ compilers are generally LP64 (or even LLP64) instead of ILP64, so "int" being possibly too small is in fact typical. Still. In the example (Java) implicit down-converting isn't allowed, so this is a result of the spec putting arbitrary limits on array size (must be indexed by nonnegative 'int' values). In C or C++ there is no such limit and I think more modern compilers (llvm) will give a warning on loss of precision, so either you have that warning ignored/disabled/unavailable or you have 32-bit code with a billion-element array. I guess what I'm thinking with this is, with a sane language/compiler, the only way to trigger this should be to fill half of your theoretically-logically-addressable memory with an array with single-byte elements.