Lecture 4.



I started with a short treatment on logarithms. Logarithms will appear in many of our complexity results so it seems prudent to get some basic facts straight from the beginning. Most importantly the log function is grows very slowly. The second point made is that the base of the logarithm does not effect the order of magnitude if the log function. In essence for any two positive bases the logBN = c logAN where c is a constant.

We then proceeded to the main topic of the lecture, namely recursion. We saw examples of two recursive algorithms. A recursive version of finding the smallest element in a list of numbers, and a recursive version of binary search. We also saw how to determine the complexity of a recursive algorithm by solving recurrence relations.

I mentioned that you can download c++ code from the author. Find the entry of our book on this page and follow the links for the source code.

Here are three versions of Binary Search in C++ the first is Weiss's the 2nd two are mine. The recursive version is direct c++ implementation of the algorithm I gave in class. By the way I started with Weiss's code to get my samples. I am being explicit about this as a reminder to you to always cite your sources and never pass off someone else's work as your own.

// BinarySearch: Return position of x in sorted array a
// or NOT_FOUND if item is not found.
// Comparable: must have operator< and operator== and all
// properties needed for vector.
template <class Comparable>
int binarySearch( const vector<Comparable> & a, const Comparable & x )
{
int low = 0;
int high = a.size( ) - 1;
int mid;

while( low < high )
{
mid = ( low + high ) / 2;

if( a[ mid ] < x )
low = mid + 1;
else
high = mid;
}
return ( low == high && a[ low ] == x ) ? low : NOT_FOUND;
}

// DR's BinarySearch: Return position of x in sorted array a
// or NOT_FOUND if item is not found.
// Comparable: must have operator< and operator== and all
// properties needed for vector.
template <class Comparable>
int DRbinarySearch( const vector<Comparable> & a, const Comparable & x )
{
int low = 0;
int high = a.size( ) - 1;
int mid;

while( low <= high )
{
mid = ( low + high ) / 2;

if (a[mid] == x) return mid;

if( a[ mid ] < x )
low = mid + 1;
else
high = mid - 1;
}
return NOT_FOUND;
}


// DR's Recusive BinarySearch: Return position of x in sorted array a
// or NOT_FOUND if item is not found.
// Comparable: must have operator< and operator== and all
// properties needed for vector.
template <class Comparable>
int DRrecursiveBinarySearch( const vector<Comparable> & a, const Comparable & x, int low, int high)
{

int mid;

if( low > high ) return NOT_FOUND;
mid = ( low + high ) / 2;
if (a[mid] == x) return mid;
if( a[ mid ] < x ) return DRrecursiveBinarySearch(a,x,mid+1, high);
if( a[ mid ] > x ) return DRrecursiveBinarySearch(a,x,low, mid-1);
}

Posted: Mon - January 17, 2005 at 04:27 PM        

©