Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Abstractions For Binary Search, Part 7: Choosing Test Cases

December 03, 2014

Last week, we took the first step toward testing our binary-search function: We wrote a linear-search function that we expect should behave the same way — with qualifications:

  • We expect the linear-search function to produce the same result as the binary-search function only in those cases where the correct outcome of the binary search is defined. For example, if we give the binary-search function an array whose elements are out of order, there is no reason to believe that the linear search will yield the same answer.
  • Our linear-search function doesn't know what goes on inside our binary-search function. Therefore, if the binary-search function happens to return what looks like a correct result, but does so through undefined or otherwise illegitimate means, comparing that result to the result of the linear search will tell us nothing about whether the binary search is working properly.

In other words, our linear-search function has given us a tool to help us test the binary-search function, but that tool is not all that we need in order to test the binary-search code completely.

Binary search is a particularly instructive algorithm to figure out how to test:

  • The essence of binary search is that it expects that its input will be properly ordered, but does not verify that expectation. Verifying that an n-element array is ordered takes O(n) time, but a binary search generally completes in O(log(n)) time, so there is no way to verify ordering without making the algorithm drastically slower.
  • Part of the input being ordered is that the order relation itself must be well behaved. That order relation is generally not supplied as part of the algorithm; instead, it is part of the type of the array elements. Accordingly, we must think about how to test code that depends for its correct operation on code that we did not write.
  • We have already noted that it is not good enough to return the correct result: A binary-search function must return the correct result without executing any undefined operations.
  • The binary-search function must search an n-element array in O(log(n)) time.

This last point is one that I think many programmers overlook when they write tests: When we choose an algorithm because of its performance characteristics, then failure to adhere to those characteristics is as much a bug as is producing the wrong result. Were that not so, we could substitute linear search for binary search and no one would be the wiser. To put it more succinctly:

Performance bugs are bugs.

These observations lead to a testing strategy:

  • We must choose an element type or types with appropriately defined comparison operations. As part of constructing our test cases, we must ensure that the comparisons are well behaved; we cannot expect either our code or test cases to detect an ill-defined comparison operation.
  • We must construct a series of test cases. Each case will consist of an array and a value to be sought in that array. When we construct these test cases, we are responsible for ensuring that the array is correctly ordered according to the comparison operation; as before, we cannot expect our code to detect an unordered input.
  • We intend to check each test case by verifying that the linear-search and binary-search functions return the same result. Moreover, we shall need to change our binary-search function to verify that it does not try to access any elements that are out of bounds, and that it is not taking an unreasonable amount of time to run.

Let us start by thinking about the type of our array elements. The only time we every look at an array element is in the condition of a single if statement:

 
if (array[mid] < x) {
           // …

This is a remarkable observation, because it means that our code never looks directly at the value of any array element; it looks only at whether each value is less than x. From this observation we can draw a conclusion that may be controversial: The actual values of the array elements don't matter! All that matters is the relative ordering of the array elements.

In other words: If the array has one or more elements, the first element could have any value at all. Each subsequent element is either greater than its predecessor or equal to it; no element can ever be less than its predecessor. For all elements past the first, these two choices are effectively all that matter. As a result, for testing purposes, for any particular value of n, we can construct a list of 2n-1 distinct arrays that is exhaustive for testing purposes. So, for example, we can construct what is essentially an exhaustive test of a binary-search algorithm on all possible 10-element arrays by using only 512 distinct arrays.

Once we have an n-element array, we need to determine that searching for every relevant value of x yields the right result. What values of x are relevant? Again, only order matters. Therefore, the relevant values are

  • Any value less than the first element of the array
  • Any value greater than the last element of the array
  • A value equal to each of the array elements
  • A value between any two adjacent array elements

These observations suggest that we can construct test cases by using odd integers and searching for all integers, even and odd, starting with zero and ending one past the last element, inclusive. For example, suppose we want to verify that we can search correctly in a four-element array. Then we would start by constructing the following eight arrays:

 
1 1 1 1
1 1 1 3
1 1 3 3
1 1 3 5
1 3 3 3
1 3 3 5
1 3 5 5
1 3 5 7
 

In each case, we would ensure that we can find correctly each integer starting from 0 and ending at one past the last array element. So, for example, for the 1 1 3 3 array, we would search for 0, 1, 2, 3, and 4, and verify that linear and binary search yield the same result.

You may argue with this strategy on the basis that it is hard to see how testing a binary-search function using only integer arrays can tell us anything about whether it will work with, say, arrays of strings. However, if we look at the code, we see that it is completely ignorant of the element types; it looks only at the result of comparisons. Because of this observation, it is hard to understand how we could ever construct a test that would pick up any bug that would affect strings and not integers, because such a test would have to verify operations that the code never performs.

This observation is an example of how knowledge of what the code does — or, in this case, what the code does not do — gives us clues about how to test the code that would be impossible to obtain without looking at the code. This example is one of the reasons that I believe that it is often essential to understand how code is constructed in order to understand how to test it.

Next week, we shall continue constructing test cases.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.