CSC161 2010F Imperative Problem Solving

Laboratory: Testing


Prerequisites: Familiarity with functions, separate compilation, and arrays.


a. Create a directory for this lab.

b. Copy into that directory two files:

c. Read bs.h to familiarize yourself with the purpose and form of the binary_search routine.


Exercise 1: Simple Tests

Let's start with some very simple tests for the routine.

a. Create a file, bstest1.c, that contains a main routine that implements the following test:

b. Create a Makefile to build a tester. You might use a rule like

jqtest1: bstest1.o jqbs.o
        $(CC) -o jqtest1 bstest1.o jqbs.o

c. Build and run your tester. Did you find any errors?

d. Add some more tests.

e. Build and run your tester. Did you find any errors?

Exercise 2: An Interactive Tester

a. Write a program, bstest2.c, that permits more interactive testing of binary_search. Your program should

Note: You may find it helpful to look at the code we wrote for the interactive tester for the average procedure.

b. Add an entry to the Makefile to build a tester for jqbs.c.

c. Build and run your tester. Did you find any errors?

Exercise 3: Systematic Testing

The tests in exercise 1 are not very systematic. For example, we never check what happens if the value is not in the array, and is between element 0 and element 1. (Surprisingly, there are many implementations of binary search which work correctly when looking between elements 1 and 2, but not between elements 0 and 1.) One advantage of using computers to do testing is that they can systematically generate a large number of tests. For example, if we generate the array { 0, 2, 4, 6, 8, 10 }, we know that

Write a tester that uses this strategy. You may also add any variants you consider appropriate.

Did you find any errors?

For Those With Extra Time

If you find yourself with extra time, implement binary search yourself.



Wednesday, 6 October 2010 [Samuel A. Rebelsk]

  • Created code files.

Friday, 8 October 2010 [Samuel A. Rebelsky]

  • Created lab.


Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri Oct 8 11:43:30 2010.
The source to the document was last modified on Fri Oct 8 11:43:28 2010.
This document may be found at
A PDF version of this document may be found at

Samuel A. Rebelsky,

Copyright © 2010 Samuel A. Rebelsky. This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. To view a copy of this license, visit or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.