Size matters: lessons from a broken binary search
Eric Shade · Journal of computing sciences in colleges · 2009
As reported in the Google Research Blog, nearly all binary search and merge sort implementations are broken because of an integer overflow bug. The bug does not appear unless the array being searched/sorted is quite large (over a billion elements), which is why it has remained undetected for decades. There is a tendency to dismiss such overflow bugs as mere trivia, but this is a mistake. This paper reviews the bug, some common but incorrect solutions, and a correct solution. More important, it distills lessons to be learned from the bug, and provides specific recommendations for computer science educators to help their students cope with such bugs in the future.