4 ms·
A research paper from Google in 2006 noted that "almost all" binary search (and merge sort) implementations contain a bug (and had for decades), so 90% seems im
by fragmede 1y ago
A research paper from Google in 2006 noted that "almost all" binary search (and merge sort) implementations contain a bug (and had for decades), so 90% seems impressive in the face of that.
https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/?m=1 https://research.google/blog/extra-extra-read-all-about-it-n...
- hiAndrewQuinn 1y agoThe bug in that paper is actually the very buffer overflow bug I was referring to. Given that Jon himself made that error in the "definitive" implementation, it seems unlikely that he would have spotted it in the 10% of implementations he considered correct. Under Google's stricter criteria it seems likely to me that not a single person got the search implementation truly correct enough.
- jansan 1y agoIn Javascript that Google "bug" only occurs if an array has more than 4503599627370495 items. You may run into memory issues before running into that bug.