Nearly All Binary Searches and Mergesorts are Broken 星期三, 六月 7 2006

每個 Programmer 都寫過既常用又簡單的 Binary Search，真的簡單嗎? From Google Research Blog

1946 年，第一個 Binary Search 演算法
1962 年，第一個 “正確” 的 Binary Search 演算法，最前面十八個都錯了.
1986 年，Jon Bentley 在課堂上和 Programming Pearls 這本書中，說明了這麼簡單的演算法(1962版)可以犯下多少的 bug.
2006 年，書中那個大眾引用的程式被抓到 integer overflow bug.

Tim Bray: (推這篇)

“If we can’t get binary search right, what chance do we have with real software?”