C++ program

binarySearch Rewrite the binary search as a template (so this one is required to be a template). So it should search int arrays, double arrays, string arrays basically any type of array where the < and > operators are defined.

Here is my function that needs to be changed into a template

#include using namespace std;

int binarySearch(const int[], int, int, int);

int main() { const int SIZE = 8; int arr[] = { 1, 5, 9, 12, 15, 21, 29, 31 }; int result; int searchNum = 9;

result = binarySearch(arr, 0, SIZE - 1, searchNum);

if (result == -1) { cout << searchNum << " is NOT in the array" << endl; }

else { cout << arr[result] << " IS in the array" << endl; }

system("PAUSE"); return 0; }

/** Searches the array anArray[first] through anArray[last] for a given value by using a binary search. @pre 0 <= first, last <= SIZE - 1, where SIZE is the maximum size of the array, and anArray[first] <= anArray[first + 1] <= ... <= anArray[last]. @post anArray is unchanged and either anArray[index] contains the given value or index == -1. @param anArray The array to search. @param first The low index to start searching from. @param last The high index to stop searching at. @param target The search key. @return Either index, such that anArray[index] == target, or -1. */ int binarySearch(const int anArray[], int first, int last, int target) { int index; if (first > last) index = -1; // target not in original array else { // If target is in anArray, // anArray[first] <= target <= anArray[last] int mid = first + (last - first) / 2; if (target == anArray[mid]) index = mid; // target found at anArray[mid] else if (target < anArray[mid]) // Point X index = binarySearch(anArray, first, mid - 1, target); else // Point Y index = binarySearch(anArray, mid + 1, last, target); } // end if

return index; } // end binarySearch