Template recursive function

[JBIRD304]

Hey guys. I'm writing a template recursive function to search for a string and an int in an array of both. The problem is that when I type in what i want to search for it finds the int but it says the string is not there even though it is! Any suggestions on where my error is?

#include <iostream>
#include <string>
using namespace std;

const int SIZE = 10;

template <class T>
bool isMember(T [] , int , int,  T val);

template <class T>
bool isMember(T ary[] , int first ,int last , T val)
{
	int middle;

	if(first > last)
		return false;
	middle = (first + last) /2;
	if(ary[middle] == val)
		return true;
	if(ary[middle]<val)
		return isMember(ary, middle+1,last, val);
	else
		return 
		isMember(ary, first,middle-1, val);
}//end isMember

int main()
{
	string sarray[SIZE] = {"Steve" , "John" , "Allen" , "Fred" , "Lonnie" , "Kim" , "Jennifer" , "Josh" , "Morgan" , "Mike" } ;
	int iarray[SIZE] = { 1, 3, 65, 44, 33, 45, 98, 87, 101, 31};

	int searchitmint;
	string searchitmstr;

	cout << "Enter a number to search for in the array: " ;
	cin >> searchitmint;
	cout << endl << endl;
	cout << "Enter a string to search for in the array: " ;
	cin >> searchitmstr;
	bool resultsint;
	bool resultsstr;
	resultsint = isMember(iarray, 0, SIZE-1 , searchitmint);
	resultsstr = isMember(sarray, 0, SIZE-1 , searchitmstr);

	if(resultsint == false)
		cout << "That number does not exist in the array! ";
	else
	{
		cout << "The number " << searchitmint << " is found in the array! " << endl << endl;
	}

	if(resultsstr == false)
		cout << "That string does not exist in the array! " << endl;
	else
	{
		cout << "The string " << searchitmstr << " is found in the array! " << endl << endl;
	}

	return 0;
}//endmain

[JBIRD304]

It seems as if it's only finding the middle value in the array

[2AoiNwbp]

When you check (middle]<val) with strings, it might not be working as you expect. Remeber "Allen" < "Steve", but you then check to the right with return isMember(ary, middle+1,last, val);, and "Steve" is to the left of the middle.

[2AoiNwbp]

To do that, I think you should sort the string array first

[JBIRD304]

So I could use a quicksort or something to sort the array and then it would work? Kind of like trying to find a word in an unsorted dictionary.

[2AoiNwbp]

Dictionaries work with sorted lists with strings (or other type) as keys. Your string would be the key you want to search, and to find it you have two choices (at least that I know), which are: search the key in a sorted list, or iterate through the list till your find you key (much slower if the list is large).

[2AoiNwbp]

I ask someone esle if dictionaries use hash tables, I know they do in Python. But I don't know how to do it with strings...

[2AoiNwbp]

I ask someone esle if dictionaries use hash tables, I know they do in Python. But I don't know how to do it with strings...

Nevermind, I think for your purpose of using you template function, you can sort your list, and then use binary search (which I think is your purpose)

[JBIRD304]

Now i did a quicksort but cant get it to run right?

#include <iostream>
#include <string>
using namespace std;

const int SIZE = 10;

// quickSort() uses the quicksort algorithm to sort array 
 //  set, from set[beg] through set[end] 
template <class T>
void quickSort(T set[], int beg, int end);
 // partition selects first value in the set as the pivot; set is
 //  arranged so that all values less than the pivot are on its 
 //  left and all the values greater than pivot are on its right
template <class T>
int partition(T set[], int beg, int end);
 
const int cnt = 10;
template <class T>
void quickSort(T set[], int beg, int end)
{
    int piv;
    if (beg < end) {
        piv = partition(set, beg, end);     // get pivot point
        quickSort(set, beg, piv - 1);       // sort first sublist
        quickSort(set, piv + 1, end);       // sort second sublist
    } // endif
} // end quickSort()

template <class T>
int partition(T set[], int beg, int end)
{
    int pivNdx = beg;               // beginning index for pivot index
    int pivot = set[beg];           // assign pivot value
    for (int k = beg + 1; k <= end; k++) {
        if (set[k] < pivot) {
            pivNdx++;
            swap(set[pivNdx], set[k]);
        } // endif
    } // endfor
    swap(set[beg], set[pivNdx]);
    return pivNdx;              // return pivot index
} // end partition()


template <class T>
bool isMember(T [] , int , int,  T val);

template <class T>
bool isMember(T ary[] , int first ,int last , T val)
{
	int middle;
	middle = (first + last) /2;
	if(first > last)
		return false;
	if(ary[middle] == val)
		return middle;
	if(ary[middle]<val)
		return isMember(ary, middle+1,last, val);
	else
		return 
		isMember(ary, first,middle-1, val);
}//end isMember

int main()
{
	string sarray[SIZE] = {"Steve" , "John" , "Allen" , "Fred" , "Lonnie" , "Kim" , "Jennifer" , "Josh" , "Morgan" , "Mike" } ;
	int iarray[SIZE] = { 1, 3, 65, 44, 33, 45, 98, 87, 101, 31};

	int searchitmint;
	string searchitmstr;
	quickSort(sarray, 0, SIZE - 1);   //sort the string array  
	cout << "Enter a number to search for in the array: " ;
	cin >> searchitmint;
	cout << endl << endl;
	cout << "Enter a string to search for in the array: " ;
	cin >> searchitmstr;
	bool resultsint;
	bool resultsstr;
	resultsint = isMember(iarray, 0, SIZE-1 , searchitmint);
	resultsstr = isMember(sarray, 0, SIZE-1 , searchitmstr);

	if(resultsint == false)
		cout << "That number does not exist in the array! " << endl;
	
	else
	{
		cout << "The number " << searchitmint << " is found in the array! " << endl << endl;
	}

	if(resultsstr == false)
		cout << "That string does not exist in the array! " << endl;
	
	else
	{
		cout << "The string " << searchitmstr << " is found in the array! " << endl << endl;
	}

	return 0;
}//endmain 

[JBIRD304]

Never mind got it! Thanks fir the help aabuezo!!