How can I make the third case a binary search and not a linear search still? I n

Question

How can I make the third case a binary search and not a linear search still? I need help figuring out how to do a binary target value search with my output files that were created? Thank you. The current code is below.

Directions:

Complete the following using C++:

1. Create data files.

You will need at least four text files filled with random integer values. You don’t need large number of values. This will just make testing easier. For example, you can create a file with a random collection of the values; 1, 2, 3, 4, 5, 6, 7, 8, & 9. Save it. Make 3 copies. In each copy put in a single value of 0: towards the beginning of one file, around the middle of another and towards the end of the third. Rename each as appropriate, i.e. early, middle, etc. Keep the original one without a 0.

2. Search for the target value (i.e. 0).

The book or the lecture has several examples of the code for searching algorithms. Implement one of them in a program that searches for the target value in your data files. Test the results.

You cannot use binary search yet. Why? Cite which one you used (page # or slide #).

3. Sort a set of values.

The book or the lecture has several examples of the code for sorting algorithms. Implement one of them in a program. Your program should write the sorted results into a file using a name the user provides. Sort all input files and compare the results. Cite which one you used (page # or slide #).

4. Search for the target value.

Find an algorithm for binary search. Implement it in a program that searches for the target value in your data file. Remember that you cannot use any of the original files since they are not sorted. Create the data files that suitable for this task, or use the output files from task 3. Cite the reference for the algorithm you use in the comment.

For this lab, you can implement each as a separate program or create a single program giving the user the choice of which activity to perform and instructions to run your program.

Here is the current code that’s compiled.

#include <iostream>

#include <fstream>

#include <stdlib.h>

#define len 10

using namespace std;

void linearSearch(int target,string file)

{

int flag=0;

ifstream in(file.c_str());

int num;

int comp=0;

while(!in.eof())

{

in>>num;

comp++;

if(num==target)

{

cout<<endl<<"Target is found in file "<<file;

cout<<endl<<"Number of comparisions: "<<comp;

flag=1;

break;

}

}

if(flag==0)

cout<<endl<<"Target is not found in file "<<file;

}

void SelectionSort(string inputfile,string outputfile)

{

ifstream in(inputfile.c_str());

int num,i=0;

int data[len+1];

int comp=0;

while(!in.eof())

{

in>>num;

data[i++]=num;

}

int j, first, temp;

i=0;

int numLength = len+1;

for (i= numLength - 1; i > 0; i--)

{

first = 0;

for (j=1; j<=i; j++)

{

comp++;

if (data[j] < data[first])

first = j;

}

temp = data[first];

data[first] = data[i];

data[i] = temp;

}

cout<<endl<<inputfile<<" is sorted after "<<comp<<" number of comparisions.";

//storing sorted data in user entered file name

ofstream out(outputfile.c_str());

for(i=0;i<len+1;i++)

out<<data[i]<<" ";

cout<<endl<<"Sorted values stored in "<<outputfile;

return;

}

int main()

{

int val;

ofstream f1("OrgFile.txt");

for(int i=0;i<len;i++)

{

f1<<(i+1)<<" ";

}

f1.close();

ofstream f2("early.txt");

ofstream f3("middle.txt");

ofstream f4("last.txt");

ifstream in("OrgFile.txt");

int num=0;

int count=0;

f2<<num<<" ";

while(!in.eof())

{

in>>num;

if(count==len/2)

{

f3<<"0"<<" ";

}

f2<<num<<" ";

f3<<num<<" ";

f4<<num<<" ";

count++;

}

f4<<"0"<<" ";

in.close();

string outputfile;

do{

cout<<"1. Search for target value (Linear Search)"<<endl;

cout<<"2. Sort set of values"<<endl;

cout<<"3. Search for target value (Binary Search)"<<endl;

cout<<"4. Exit"<<endl;

cin>>val;

switch(val){

case 1:

cout<<endl<<"Result of searching the target value 0, using linear search algorithm.";

linearSearch(0,"early.txt");

linearSearch(0,"middle.txt");

linearSearch(0,"last.txt");

break;

case 2:

cout<<endl<<"Result of Sorting the files using selection sort algorithm";

cout<<endl<<"Enter a file name to store result: ";

cin>>outputfile;

SelectionSort("early.txt",outputfile);

cout<<endl<<"Enter a file name to store result: ";

cin>>outputfile;

SelectionSort("middle.txt",outputfile);

cout<<endl<<"Enter a file name to store result: ";

cin>>outputfile;

SelectionSort("last.txt",outputfile);

break;

case 3:

cout<<endl<<"Result of searching user entered target value, using linear search algorithm.";

int target;

cout<<endl<<"Enter a target value to search: ";

cin>>target;

linearSearch(target,"early.txt");

linearSearch(target,"middle.txt");

linearSearch(target,"last.txt");

break;

case 4:

exit(0);

}

}while(true);

return 0;

}

Explanation / Answer

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <algorithm>
#define len 10
using namespace std;

void linearSearch(int target,string file)
{
int flag=0;
ifstream in(file.c_str());
int num;
int comp=0;
while(!in.eof())
{
in>>num;
comp++;
if(num==target)
{
cout<<endl<<"Target is found in file "<<file;
cout<<endl<<"Number of comparisions: "<<comp;
flag=1;
break;
}
}
if(flag==0)
cout<<endl<<"Target is not found in file "<<file;
}

void binarySearch(int target,string file)
{
int flag=0;
ifstream in(file.c_str());
int num;
int comp=0;
int index=0;
int arr[1000];
while(!in.eof())
{
in>>num;
arr[index++] = num;
}
sort(arr, arr+index);
int l = 0;
int h = index - 1;
while (l <= h) {
   int mid = (l + h) / 2;
   if(arr[mid]==target){
   comp++;
   flag = 1;
   break;
   }
   if (target > arr[mid]) {
   comp+=2;
       l = mid + 1;
   } else {
       h = mid - 1;
   }

}
if(flag==1)
{
cout<<endl<<"Target is found in file "<<file;
cout<<endl<<"Number of comparisions: "<<comp;
}else
cout<<endl<<"Target is not found in file "<<file;

}
void SelectionSort(string inputfile,string outputfile)
{

ifstream in(inputfile.c_str());
int num,i=0;
int data[len+1];
int comp=0;
while(!in.eof())
{
in>>num;
data[i++]=num;
}

int j, first, temp;
i=0;
int numLength = len+1;
for (i= numLength - 1; i > 0; i--)
{
first = 0;
for (j=1; j<=i; j++)
{
comp++;
if (data[j] < data[first])
first = j;
}
temp = data[first];
data[first] = data[i];
data[i] = temp;
}
cout<<endl<<inputfile<<" is sorted after "<<comp<<" number of comparisions.";
//storing sorted data in user entered file name
ofstream out(outputfile.c_str());
for(i=0;i<len+1;i++)
out<<data[i]<<" ";
cout<<endl<<"Sorted values stored in "<<outputfile;

return;
}

int main()
{
int val;
ofstream f1("OrgFile.txt");
for(int i=0;i<len;i++)
{
f1<<(i+1)<<" ";
}
f1.close();

ofstream f2("early.txt");
ofstream f3("middle.txt");
ofstream f4("last.txt");
ifstream in("OrgFile.txt");
int num=0;
int count=0;
f2<<num<<" ";
while(!in.eof())
{
in>>num;
if(count==len/2)
{
f3<<"0"<<" ";
}
f2<<num<<" ";
f3<<num<<" ";
f4<<num<<" ";
count++;
}
f4<<"0"<<" ";
in.close();
string outputfile;
do{
int target;
cout<<"1. Search for target value (Linear Search)"<<endl;
cout<<"2. Sort set of values"<<endl;
cout<<"3. Search for target value (Binary Search)"<<endl;
cout<<"4. Exit"<<endl;
cin>>val;
switch(val){
case 1:
cout<<endl<<"Result of searching the target value 0, using linear search algorithm.";
linearSearch(0,"early.txt");
linearSearch(0,"middle.txt");
linearSearch(0,"last.txt");
cout<<endl<<"Result of searching user entered target value, using linear search algorithm.";
cout<<endl<<"Enter a target value to search: ";
cin>>target;
linearSearch(target,"early.txt");
linearSearch(target,"middle.txt");
linearSearch(target,"last.txt");
break;
case 2:
cout<<endl<<"Result of Sorting the files using selection sort algorithm";

cout<<endl<<"Enter a file name to store result: ";
cin>>outputfile;
SelectionSort("early.txt",outputfile);
cout<<endl<<"Enter a file name to store result: ";
cin>>outputfile;
SelectionSort("middle.txt",outputfile);
cout<<endl<<"Enter a file name to store result: ";
cin>>outputfile;
SelectionSort("last.txt",outputfile);
break;

case 3:
cout<<endl<<"Result of searching user entered target value, using binary search algorithm.";
cout<<endl<<"Enter a target value to search: ";
cin>>target;
binarySearch(target,"early.txt");
binarySearch(target,"middle.txt");
binarySearch(target,"last.txt");

break;


case 4:
exit(0);
}

}while(true);
return 0;
}
=========================================================
I have added binarySearch Method. Please Test and let me know if there is any concern.

Thanks

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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