Comment by ckcheng
18 hours 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-n...
403 error. What was the bug?
Load in an incognito window?
Loads fine for me:
> The bug is in this line:
6: int mid =(low + high) / 2;
IIRC 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.
64KiB was common in the 16-bit era, however