Nearly All Binary Searches and Mergesorts are Broken

每個 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?"

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s