Question

You are making a .h file. Implement a recursive binary search function. bSearch passes in an array of integers, the size of the array, and the value the function is searching for. The function should return the index where found or -1 if not found. You will want to implement a recursive helper function that passes in the array, the value to be located, and the beginning and ending of the range of values to search within. Use the provided main function to test your search function. Be sure not to use a loop of any kind in any of the functions you write.

#include using namespace std; #include "BinarySearch.h" int main() { int choice = 1; cin >> choice; if (choice == 1) { int arr[] = {1, 5, 8, 10, 14, 15}; cout << bSearch(arr, 6, 1) << endl << bSearch(arr, 6, 0) << endl << bSearch(arr, 6, 15) << endl << bSearch(arr, 6, 14) << endl; } else if (choice == 2) { int arr2[] = {-178, -148, -99, -87, -75, -42, -23, -2}; cout << bSearch(arr2, 8, -2) << endl << bSearch(arr2, 8, -178) << endl << bSearch(arr2, 8, -148) << endl << bSearch(arr2, 8, 1) << endl << bSearch(arr2, 8, -179) << endl << bSearch(arr2, 8, -1) << endl; } else { int arr3[] = {100}; cout << bSearch(arr3, 1, 100) << endl << bSearch(arr3, 1, -15) << endl << bSearch(arr3, 1, 115) << endl; } return 0; }

Answer 1

// BinarySearch.h
int bSearchHelper(int array[], int left, int right, int target)
{
if (right >= left)
{
int mid = left + (right - left)/2;

if (array[mid] == target) return mid;

if (array[mid] > target) return bSearchHelper(array, left, mid-1, target);

return bSearchHelper(array, mid+1, right, target);
}

return -1;
}

int bSearch(int array[], int size, int target)
{
   return bSearchHelper(array,0, size-1, target);
}

// main.cpp

#include <iostream>
#include "BinarySearch.h"
using namespace std;

int main ()
{
   int choice = 1;
   cin >> choice;

   if(choice == 1)
   {
       int arr[] = {1,5,8,10,14,15};
       cout << bSearch(arr,6,0) << endl
           << bSearch(arr,6,0) << endl
           << bSearch(arr,6,15) << endl
           << bSearch(arr,6,14) << endl;
   }
   else if(choice == 2)
   {
       int arr2[] = {-178,-148,-99,-87,-75,-42,-23,-2};
       cout << bSearch(arr2,8,-2) << endl
           << bSearch(arr2,8,-178) << endl
           << bSearch(arr2,8,-148) << endl
           << bSearch(arr2,8,1) << endl
           << bSearch(arr2,8,-179) << endl
           << bSearch(arr2,8,-1) << endl;
   }
   else
   {
       int arr3[] = {100};
       cout << bSearch(arr3,1,100) << endl
           << bSearch(arr3,1,-15) << endl
           << bSearch(arr3,1,115) << endl;
   }
return 0;
}