public marks

PUBLIC MARKS from feision with tags programming & code

24 July 2006 22:15

FrogBSD Blog » Nearly All Binary Searches and Mergesorts are Broken

Nearly All Binary Searches and Mergesorts are Broken Filed under: Programming — zmx @ 10:40 am 每個 Programmer 都寫過既常用又簡單的 Binary Search,真的簡單嗎? From Google Research Blog 1946 年,第一個 Binary Search 演算法 1962 年,第一個 “正確” 的 Binary Search 演算法,最前面十八個都錯了. 1986 年,Jon Bentley 在課堂上和 Programming Pearls 這本書中,說明了這麼簡單的演算法(1962版)可以犯下多少的 bug. 2006 年,書中那個大眾引用的程式被抓到 integer overflow bug.