3 ms·
It is famously difficult to implement binary search correctly.
by civopsec 4y ago
It is famously difficult to implement binary search correctly.
- karmakaze 4y agoHow so, integer overflow? Not so famous that I'm aware.
- mason55 4y ago> Not so famous that I'm aware https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
- kragen 4y agoit took about ten years from the time of the first purported publication of a binary search algorithm for a correct algorithm to be published it's an algorithm where it's easy to have off-by-one errors that lead to nontermination or incorrect results for certain inputs integer overflow is also a problem on some platforms, especially java
- ilyt 4y agoI doubt someone spent 10 years trying to implement a binary search. I suspect it is as usual, someone made theoretical invention, then someone else looked at it years later and wrote implementation in evening or two
- kragen 4y agomore likely there were a lot of correct implementations, but they got debugged after the initial publication, and then didn't publish the erratum