Introduction
In the fourth chapter of “Programming Pearls”, Jon Bentley discusses program correctness and tells us that as part of some of his programming classes, he asks the attendees to implement the binary search algorithm. Although simple in appearance (“look at the middle element, if it’s the target terminate, if it’s smaller look in the upper half, otherwise look in the lower half”), it can be a surprisingly tricky algorithm to implement. He cites TAoCP Vol. 3 wherein Don Knuth mentions that although the first paper on binary