4 ms·
Took a few more years to get really bug free. > Fast forward to 2006. I was shocked to learn that the binary search program that Bentley proved correct and sub
by ckcheng 2mo ago
Took a few more years to get really bug free.
> Fast forward to 2006. I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. ... Lest you think I'm picking on Bentley, let me tell you how I discovered the bug: The version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so.
https://research.google/blog/extra-extra-read-all-about-it-nearly-all-binary-searches-and-mergesorts-are-broken/ https://research.google/blog/extra-extra-read-all-about-it-n...
- inigyou 2mo ago403 error. What was the bug?
- _dain_ 2mo agoIIRC it was overflow when you do (a + b) / 2 for the midpoint. It took so long to find because you need a >billion item array to overflow the 32-bit integer, and that much RAM wasn't common until the 00s. The right way is a + (b - a)/2.
- inigyou 2mo ago64KiB was common in the 16-bit era, however
- fragmede 2mo agoLoad in an incognito window? Loads fine for me: > The bug is in this line: 6: int mid =(low + high) / 2;