Download the binary search code skeleton. $ wget ftp://bits.use.edu/csl03/lab-bi

Question

Download the binary search code skeleton. $ wget ftp://bits.use.edu/csl03/lab-binsearch.tar $ tar xvf lab-binsearch.tar $ cd lab-binsearch This will extract the following files: binsearch.epp // skeleton code you will modify sorted_data.in // sorted list of integers to search unsorted_data.in // unsorted list of integers to search Now make the following alterations: 1. Examine the list of integers in sorted_data. in and unsorted_data. in which your code will need to search through for a value provided by the user (via cin). 2. Open binsearch.epp and examine and understand the skeleton code. As a point of interest understand the code that counts how many integers are in the file before reading them in. 3. Implement a recursive binary search algorithm in the binsearch() function. a. You may NOT use any explicit while/for loops...you must use recursion b. Remember the start index is inclusive but the end index is exclusive (i.e. 1 beyond the actual last index to be searched). 4.

Explanation / Answer

binsearch.cpp

#include <iostream>
#include <fstream>

using namespace std;

void sort(int *, int);
int binsearch(int, int *, int, int);

int main(int argc, char *argv[]){
int target;
if(argc < 2){
cout << "Provide a filename of the data to be searched" << endl;
return 1;
}
ifstream datfile(argv[1], ios::in);
if( datfile.fail() ){
cout << "Unable to open file: " << argv[1] << endl;
return 1;
}
int count = 0;
// Count how many integers are in the file
while(! datfile.fail()){
int temp;
datfile >> temp;
if(!datfile.fail()){
count++;
}
}
// When we reach the end of the file, the EOF flag is set
// To be able to read through the file again we need to clear that flag
datfile.clear();
// We also need to set our internal position in the file back to 0
datfile.seekg(0,ios::beg);

// Now allocate an array to store the file data and read in the data
int *data = new int[count];
for(int i=0; i < count; i++){
datfile >> data[i];
}

datfile.close();

cout << "Read " << count << " integers from the data file. " << endl;
cout << "Enter the target positive integer to search for: ";
cin >> target;

// Uncomment the line below for part 2
// sort(data, count);

// Call binary search
int retval = binsearch(target,data,0,count);

// Interpret and print the results
if(retval == -1){
cout << target << " does not appear in the data." << endl;
}
else {
cout << target << " appears at index " << retval << " in the data." << endl;
}

// Deallocate the data array
delete [] data;
return 0;
}

// Returns the index in the data array where target is located
// or -1 if the target value is not in the list
int binsearch(int target, int *data, int start, int end)
{
   if(start==end)
   {
       return -1;
   }
   int mid=(start+end)/2;
  
   if(data[mid]==target)
   {
       return mid;
   }
   else if(data[mid]<target)
   {
       return binsearch(target,data,mid+1,end);
   }
   else
   {
       return binsearch(target,data,start,mid);
   }
}

// implements a selection sort algorithm to sort
// the integer values in the 'data' array of size 'len'
// You aren't allowed to change the prototype of this function
void sort(int *data, int len)
{

}

sample output:

./binsearch sorted_data.in

Read 20 integers from the data file.

Enter the target positive integer to search for: 33

33 appears at index 15 in the data.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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