C++ program binarySearch – Rewrite the binary search as a template (so this one

Question

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

Explanation / Answer

Answer:

#include<iostream.h>

void main()
{
  
   int n, i, input[50], find, begin, end, between;
   cout<<"Enter total number of elements :";
   cin>>n;
   cout<<"Enter "<<n<<" number :";
   for (i=0; i<n; i++)
   {
       cin>>input[i];
   }
   cout<<"Enter a number to find :";
   cin>>find;
   begin = 0;
   end = n-1;
   between = (begin+end)/2;
   while (begin <= end)
   {
       if(input[between] < find)
       {
           begin = between + 1;

       }
       else if(input[between] == find)
       {
           cout<<find<<" found at location "<<between+1<<" ";
           break;
       }
       else
       {
           end = between - 1;
       }
       between = (begin + end)/2;
   }
   if(begin > end)
   {
       cout<<"Element Not found "<<find<<" is not present in the list.";
   }

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.