O'Reilly logo

Beautiful Code by Andy Oram, Greg Wilson

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Nailing Binary Search

Given its history, I am not going to be fooled by the apparent simplicity of binary search, or by the obviousness of the fix, especially because I've never used the unsigned bit shift operator (i.e., >>>) in any other code. I am going to test this fixed version of binary search as if I had never heard of it before, nor implemented it before. I am not going to trust anyone's word, or tests, or proofs, that this time it will really work. I want to be confident that it works as it should through my own testing. I want to nail it.

Here's my initial testing strategy (or team of tests):

  • Start with smoke tests.

  • Add some boundary value tests.

  • Continue with various thorough and exhaustive types of tests.

  • Finally, add some performance tests.

Testing is rarely a linear process. Instead of showing you the finished set of tests, I am going to walk you through my thought processes while I am working on the tests.

Smoking Allowed (and Encouraged)

Let's get started with the smoke tests. These are designed to make sure that the code does the right thing when used in the most basic manner. They are the first line of defense and the first tests that should be written, because if an implementation does not pass the smoke tests, further testing is a waste of time. I often write the smoke tests before I write the code; this is called test-driven development (or TDD).

Here's my smoke test for binary search:

 import static org.junit.Assert.*; import org.junit.Test; public class BinarySearchSmokeTest ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required