Comment by amtamt
20 hours ago
If bug free binary search implementation can take 16 years, I am ready to buy generics implementation could take 20 years.
> In his landmark book The Art of Computer Programming, legendary computer scientist Donald Knuth noted that although the first binary search algorithm was published by John Mauchly in 1946, the first bug-free version was not published until 1962—taking a staggering 16 years to get right.
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.
1 reply →