Please write in C++. Thank you in advance. Requested files : BinarySearch.h, Bin
ID: 3839492 • Letter: P
Question
Please write in C++. Thank you in advance.
Requested files: BinarySearch.h, BinarySearch.cpp, BinarySearch_test.cpp
Write a program that will use a recursive binary search to locate an integer in a sorted array. The integer values will be provided in a file named dataarray.bin. You should dynamically allocate memory sufficient to hold all elements in this array and read the contents of this file into your data structure.
Your code must implement a function called recursiveBinarySearch(int start_index, int end_index, int_targetValue) which will perform the binary search for the integer value entered at the command line.
If the value is found you should print a string "N:V" where N is the number of comparisons made before the value V is found. If the value V is not found in the array print a dash, for example "23:-"
You should test you class with a driver program named BinarySearch_test.cpp
Explanation / Answer
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<vector>
using namespace std;
//vector to dynamically store large number of values...
vector<unsigned int> ret; //std::list may be preferable for large files
//variable to count the number of comparisions...
int n=0;
//method to read file....
void readBinaryFile(char* fileName)
{
ifstream read(fileName);
unsigned int current;
if(read!=NULL)
while (read>>current) {
ret.push_back(current);
}
}
//recursive binary search method
void recursiveBinarySearch(int start_index, int end_index, int targetValue)
{
int mid = (start_index+end_index)/2;
if(start_index>end_index)
{
cout<<n<<":-"<<endl;
return ;
}
if(ret.at(mid)==targetValue)
{
n++;
cout<<n<<":"<<mid<<endl;
return ;
}
else if(ret.at(mid)<targetValue)
{
n=n+2;//upto here two comparisions have been made..so adding two
start_index=mid+1;
return recursiveBinarySearch(start_index,end_index,targetValue) ;
}
else
{
n=n+2;
end_index=mid-1;
return recursiveBinarySearch(start_index,end_index,targetValue) ;
}
}
//tester method
int main()
{
char a[] ="dataarray.bin";
//assuming that all integers in file are already in sorted order
readBinaryFile(a);
int targetValue;
cout<<"Enter a Value to search:";
cin>>targetValue;
recursiveBinarySearch(0,ret.size()-1,targetValue) ;
return 0;
}
//bin file
//dataarray.bin
1 2 3 4 5 6 7 8
output1:
Enter a Value to search:2
3:1
Process exited normally.
Press any key to continue . . .
output2:
Enter a Value to search:40
8:-
Process exited normally.
Press any key to continue . . .
output1: