Recursive Function

TriggerJ · 02-02-2004, 02:10 PM

How would I change the binarySearch function into a recursive function in the following program?

Thanks,

Jessica

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <iomanip>

using std::setw;

int binarySearch (const int [], int, int, int, int);
void printHeader (int);
void printRow (const int [], int, int, int, int);

int main ()
{
const int arraySize=15;
int a [arraySize];
int key;

for (int i=0; i<arraySize; i++)
a[i]=2*i;

cout<< "Enter a number between 0 and 28: ";
cin>>key;

printHeader (arraySize);

int result =
binarySearch (a, key, 0, arraySize-1, arraySize);

if (result != -1)
cout<< '\n'<<key<< " found in array element "
<<result<<endl;
else
cout<<'\n'<<key<<" not found"<<endl;
return 0;
}

int binarySearch(const int b[], int searchKey, int low, int high, int size)
{
int middle;

while (low <= high)
{
middle= (low+high)/2;
printRow(b, low, middle, high, size);

if (searchKey == b[middle])
return middle;
else
if (searchKey<b[middle])
high=middle-1;
else
low=middle+1;
}
return -1;
}

void printHeader(int size)
{
cout<<"\nSubscripts:\n";

for (int j=0; j<size; j++)
cout <<setw (3)<<j<<' ';

cout<<'\n';

for (int k=1; k<=4*size; k++)
cout<<'-';

cout<< endl;
}

void printRow(const int b[], int low, int mid, int high, int size)
{
for (int m=0; m<size; m++)

if (m<low||m>high)
cout<<" ";
else
if (m==mid)
cout <<setw(3)<<b[m]<<'*';
else
cout<<setw(3)<<b[m]<<' ';
cout<<endl;
}

Strike · 02-02-2004, 02:48 PM

Smells like homework.

crabboy · 02-02-2004, 04:50 PM

Code:

int binarySearch(const int b[], int searchKey, int low, int high, int size)
{
   int middle;

   middle = ( low + high ) / 2;
   printRow(b, low, middle, high, size);

   if ( searchKey > b[middle] )
      return binarySearch( b, searchKey, middle + 1 , high, size );
   else if ( searchKey < b[middle] )
      return  binarySearch( b, searchKey, low , middle - 1, size );
   else if ( searchKey == b[middle] )
      return middle;

   return -1;
}

TriggerJ · 02-02-2004, 08:02 PM

Thank you!!!

wapcaplet · 02-02-2004, 08:58 PM

Recursive functions are almost always a bad idea, though. Stack overflows and stuff can be nasty. If you have a non-recursive algorithm, it'd be better to stick with that.