templateBS

#include <iostream>
#include<string>
using namespace std;
const int ARRAY_SIZE = 8;
template<class T>
void recBinSrch(const T a[], int first, int last,
	T key, bool& found, int& location);
//Precondition:  Type T must support = == and >
//a[first] through a[last] are sorted in increasing order.
//Postcondition:
//if key is not one of the values a[first] through a[last],
//then found == false;
//otherwise a[location] == key and found == true.

template<class T>
void ItrSearch(const T a[], int low, int high,
	T key, bool& found, int& location);
//Precondition: Type T must support = == and >
// a[first] through a[last] are sorted in increasing order.
//Postcondition: if key is not one of the values a[first] through a[last],
//then found == false; otherwise a[location] == key and found == true.

int main()
{
	const int finalIndex = ARRAY_SIZE - 1;

	int i;
	double a[] = { 3.3 , 6.6 , 8.8 , 9.9 , 11.1 , 15.1 , 16.1 , 20.2 };
	std::string b[] = { "aaa", "abc", "ahh", "bde", "bee", "ccc", "feg", "hee" };
	int c[] = { 15, 33, 45, 46, 49, 59, 70, 81 };
	//test int
	cout << "Array contains:\n";
	for (i = 0; i < ARRAY_SIZE; i++)
		cout << c[i] << " ";
	cout << endl;
	int key, location;
	bool found;
	cout << "Enter number to be located: ";
	cin >> key;

	cout << "\nTesting Template Iterative Binary Search\n";
	ItrSearch(c, 0, finalIndex, key, found, location);
	if (found)
		cout << key << " is in index location "
		<< location << endl;
	else
		cout << key << " is not in the array." << endl;


	cout << "\nTesting Template Recursive Binary Search\n";
	recBinSrch(c, 0, finalIndex, key, found, location);
	if (found)
		cout << key << " is in index location "
		<< location << endl;
	else
		cout << key << " is not in the array." << endl;

	//test string
	std::string keyString;
	cout << endl;
	cout << "Array contains:\n";
	for (i = 0; i < ARRAY_SIZE; i++)
		cout << b[i] << " ";
	cout << endl;
	cout << "Enter string to be located: ";
	cin >> keyString;

	cout << "\nTesting Template Iterative Binary Search\n";
	ItrSearch(b, 0, finalIndex, keyString, found, location);
	if (found)
		cout << keyString << " is in index location "
		<< location << endl;
	else
		cout << keyString << " is not in the array." << endl;


	cout << "\nTesting Template Recursive Binary Search\n";
	recBinSrch(b, 0, finalIndex, keyString, found, location);
	if (found)
		cout << keyString << " is in index location "
		<< location << endl;
	else
		cout << keyString << " is not in the array." << endl;
	//test double
	double keydouble;
	cout << endl;
	cout << "Array contains:\n";
	for (i = 0; i < ARRAY_SIZE; i++)
		cout << a[i] << " ";
	cout << endl;
	cout << "Enter number to be located: ";
	cin >> keydouble;

	cout << "\nTesting Template Iterative Binary Search\n";
	ItrSearch(a, 0, finalIndex, keydouble, found, location);
	if (found)
		cout << keydouble << " is in index location "
		<< location << endl;
	else
		cout << keydouble << " is not in the array." << endl;


	cout << "\nTesting Template Recursive Binary Search\n";
	recBinSrch(a, 0, finalIndex, keydouble, found, location);
	if (found)
		cout << keydouble << " is in index location "
		<< location << endl;
	else
		cout << keydouble << " is not in the array." << endl;
	return 0;
}

template<class T>
void recBinSrch(const T a[], int first, int last,
	T key, bool& found, int& location)
{
	int mid;
	if (first > last)
	{
		found = false;
	}
	else
	{
		mid = (first + last) / 2;
		if (key == a[mid])     // T must support ==
		{
			found = true;
			location = mid;
		}
		else if (a[mid] > key) // T must support >
		{
			recBinSrch(a, first, mid - 1, key, found, location);
		}
		else if (key > a[mid])   // Changed to avoid requiring >
		{
			recBinSrch(a, mid + 1, last, key, found, location);
		}
	}
}

template<class T>
void ItrSearch(const T a[], int low, int high, T key, bool& found, int& location)
{
	int first = low;
	int last = high;

	int mid;

	found = false;
	while ((first <= last) && !found)
	{
		mid = (first + last) / 2;

		if (key == a[mid]) //T must support ==
		{
			found = true;
			location = mid;
		}
		else if (a[mid] > key) // T must support >
			last = mid - 1;
		else if (key > a[mid])  // Changed to avoid requiring >
			first = mid + 1;
	}
}