Beautiful Code: Testing a Binary Search Implementation

The Binary Search algorithm has been around for quite a while. I remember doing an implementation (in Fortran) as part of course work in 1977. Hence it was a surprise to read about it in Joshua Bloch's blog post. I am  pretty sure that what I, and the rest of the course, implemented had the same defect.

Alberto Savola in his essay "Beautiful Tests" in Beautiful Code, quotes Donald Knuth as saying that though the first binary search was published in 1946, it took 12 more years for the first binary search without bugs to be published. However, defective implementations could, and did recur.

All very humbling. To quote Joshua, "The general lesson that I take away from this bug is humility".

Alberto Savola's piece uses the Binary Search program to show how tests should be developed. Here are some topics that I found educative:

• The utility of smoke tests.
• Re-factoring code to improve testability. A side-effect of this is to improve the design and the readability of the program.
• The design of tests to verify that neither a true condition is detected as false nor a false condition detected as true. What in radar theory are called failed detection and false alarm.
• Formulating theories (I think calling them hypotheses, would be more appropriate) of the forms: If A is true then B should be true; If A is not true then B should not be true. 
• Random generation of tests. This is most intriguing. I wonder if genetic algorithms could be used to generate tests.
• The use of helper tests that give an alternate way of checking. These are simple tests whose correctness are easy to verify by visual inspection. For the binary search a test using a linear search is also implemented. The linear search is used to cross check results obtained using the binary search.

A quote from Savola:
"Truly beautiful testing requires a developer to make an effort, think outside the box, explore weird scenarios, look for weaknesses, and try to break things".
(Note 1: The emphasis is mine.
Note 2: A side note: "outside the box", I think, is a more appropriate expression, in such contexts, rather than the more commonly used "out of the box".)