CS 202 Fall 2013
In-Class Challenge for Thursday, December 5, 2013

Our Goal

We wish to write a recursive function template binSearch that does Binary Search, returning true if the given value is found, and false if it is not.

Prototype binSearch as follows.

[C++]

template <typename Iter, typename Value>
bool binSearch(Iter first, Iter last, const Value & key);

The function is given a range specified by two random-access iterators: first and last, in the usual way. It might be called as follows.

[C++]

vector<int> v;

int tofind = 42;
bool found = binSearch(v.begin(), v.end(), tofind);
if (found)
{
    ~~~

Some (Hopefully) Helpful Things

How Recursive Binary Search

Find the size of the given range. This is last - first. Save this in a variable.

You will need a base case: when size < 1. What is the result when size == 0? What is the result when size == 1?

Then comes the recursive case. Make an iterator to the middle of the range (first + size/2). Compare the key to the item this points to. Is the key less? Then do a recursive call on the first half of the range, and return its result. Otherwise, do a recursive call on the second half, and return its result.

Skeleton File

I have provided an unfinished version of header binsearch.h. You may wish to start your work with it, to save time.

What to Do

1. Write function template binSearch, in header binsearch.h. Since this is a template, there is no associated source file. The resulting code should compile and pass all tests in the given test program: test_binsearch.cpp.