The bug only manifests if the range you're searching is within MAX_INT/2 (or whatever numeric datatype you're using). I'm not sure I understand the point you're trying to make.
I didn't understand what you were talking about offhand and thought range might be the value of the stored/searched data, not a pointer arithmetic issue.
When the array/list consumes a memory footprint larger than ptrdiff_t it was possible that the specific implementations might fail. It is crucial to remember that the difference between memory address is signed and that the size of objects (even if bare machine integers of some size) in the set might be displayed as a number smaller than one of the powers of two many recall.
On a 32 bit machine this wouldn't be approx 2 billion but rather often 500M 32 bit words or 250M-ish 'double' precision numbers. Let alone if the search is over more complex structures representing objects. For a smaller 16-bit embedded system I could even more readily see this occurring.
You make a good point. I was actually speaking about the general case, where you're simply pulling the bounds of x_min and x_max closer until f(x) reaches a target value or the bounds converge to the same value. f could be an array and x could be an index, but it doesn't have to be. The bug still exists in this general case. All you need is a numerical datatype that can overflow, and most of them can.
Yet you focus only on one aspect of the linked discussion on the high rate of misimplementations, an aspect that represents the least relevant part, and then act as if this invalidates the point?
I didn't say it invalidates the point, because I honestly don't know what your point was to begin with. Which is why I asked the question originally. I'm still no closer to knowing, and it seems like you're not interested in elaborating. Suit yourself.
This is an extremely disingenuous reply as well. You started off your first reply by saying “the bug only manifests ...” already pre-supposing that the scope of my original comment was restricted to that one thing, and tacitly ignoring all the other aspects of the link.
The (obvious) point is that binary search is widely misimplemented even by professionals writing textbooks (and this had little to do with the specific Java bug responsible for that one example), and this is all stated directly in the link you didn’t read.
It’s comically ill-suited for time based tech screens as even experts teaming with editors often still get it wrong.
When the array/list consumes a memory footprint larger than ptrdiff_t it was possible that the specific implementations might fail. It is crucial to remember that the difference between memory address is signed and that the size of objects (even if bare machine integers of some size) in the set might be displayed as a number smaller than one of the powers of two many recall.
On a 32 bit machine this wouldn't be approx 2 billion but rather often 500M 32 bit words or 250M-ish 'double' precision numbers. Let alone if the search is over more complex structures representing objects. For a smaller 16-bit embedded system I could even more readily see this occurring.