4 ms·
The overflow bug wasn't fixed until the 21st century; the comment you remember reading dates from before it was discovered. To be fair, in most computing envir
by kragen 1y ago
The overflow bug wasn't fixed until the 21st century; the comment you remember reading dates from before it was discovered.
To be fair, in most computing environments, either indices don't overflow (Smalltalk, most Lisps) or arrays can never be big enough for the addition of two valid array indices to overflow, unless they are arrays of characters, which it would be sort of stupid to binary search. It only became a significant problem with LP64 and 64-bit Java.
- eru 1y agoAgreed. Your comment is mostly true, when you do binary search in something like an array, yes. But you can also do binary search in any monotonically increasing function.
- kragen 1y agoFor arbitrary functions you usually want floating point, which solves the overflow problem in a different way.