Consider a binary search function. If no match is found, the function returns -1
ID: 3724299 • Letter: C
Question
Consider a binary search function. If no match is found, the function returns -1. Modify the function so that it returns a bool value that indicates whether a match was found. Add a reference parameter m, which is set to the location of the match if the search was successful. If a was not found, set m to the index of the next larger value instead, or to a.size) if a is larger than all the elements of the vector.
Implement a function bool binary.search (vector & v, int value, int & m) , that uses binary search to find out whether there is an integer value in the vector v of integers. If a match is found, the function returns true, otherwise it returns false. In the above function m is a reference parameter, which must be set to the location of the match if the search was successful. If value were not found, set m to the index of the next larger value instead, or to v.size () if value is larger than all the elements of the vector . Write a program that reads the list of integers from a file data3.txt and displays them on the screen. Then the program must sort the numbers using sort function from C++ library and then display the sorted vector .Finally, implement a loop in which the user is asked to enter a value, which is then searched in the sorted array using the above binary.search function. If value is found display "Found. m-, followed by the value of m. Otherwise display "Not found. m-” followed by the value of m. . You can assume that data3.txt contains only integers (no floating point numbers or strings that are not numbers) and that the file has at least one number . Submit the solution as hmw-5-3.cpp . Sample input-output data3.txt - Not. ClWin exe File Edit Format View Help Before sorting 2 3 4543 21-1 fter sorting: 1 1 1 2 2 3 344 5 Enter a value 2 Found. n-4 ontinueExplanation / Answer
/*
Binary Search: Binary search is a searching techniques which search element in sorted sequence by eliminating half of elements in
each iteration/step.
Algorithm:
left=0,right=arr.size-1
1.find middle=(left+right)/2
2.if(arr[middle]==search_key) return mid;
3.if(arr[middle]<search_key) middle=left+1 //search in right half
4. else search in left half middle =right-1
5. repeat 1,2,3,4
I used many function of vector , Code is well commented , please read comment carefully to understand better.
Sample Output:
Before sorting:
1 2 3 4 5 4 3 2 1 -1
After sorting:
-1 1 1 2 2 3 3 4 4 5
Enter a value: 2
Found. m=4
Continue(y/n)?y
Enter a value: 0
Not found. m=1
Continue(y/n)?n
*/
//Please copy the code from below line to the end of answer to your hmw_3_5.cpp
//C++ Program to read data from file sort them and perform binary search
#include<iostream> //standard input/out like cin and cout
#include <vector> //Create vector
#include<fstream> //Open file connection
#include <algorithm> // To include sort function of vector
using namespace std;
//BInary search function
bool binary_search(vector<int> &v,int value, int &m)
{
int left=0;
int right=v.size()-1;
//Loop until left greater than right
while(left<=right)
{
//Find the mid index
int mid=(left+right)/2;
if(v.at(mid)==value) //If element set the m and return
{
m=mid;
return true;
}
else if(v.at(mid)<value) //search in right half
{
left=mid+1;
}
else //Search in left half
{
right=mid-1;
}
}
//setting m=left because left will always point right position in case element not present.
m=left;
//returning false
return false;
}
//Main function
int main()
{
//Declaring vector variable
vector <int> v;
//Declaring other variables
int value,m;
char choice;
bool retVal;
//Declaring myfile variable
ifstream myfile;
//Opening file
myfile.open("data3.txt");
//error check, if file not found
if (myfile.fail())
{
cout << "file read failure, check source" << endl;
exit(0);
}
int num=0;
//Reading till the last entry of file, we are reading line by line
while (myfile.eof() ==0)
{
//Reading single integer from file
myfile>>num;
//If reached at end of file stop the next iteration, If you will remove this line it will add last entry twice.
if (myfile.eof())
break;
//Adding num to v
v.push_back(num);
}
//Displaying vector entries
cout<<"Before sorting:"<<endl;
int i;
for (i = 0; i < v.size(); i++)
{
cout << v.at(i)<<" ";
}
//Sorting the vector
sort(v.begin(),v.end());
cout<<" After sorting:"<<endl;
for (i = 0; i < v.size(); i++)
cout << v.at(i)<<" ";
//creating menu , Loop will run infinitely until you enters n character
//do-while loop start here
do{
cout<<" Enter a value: ";
cin>>value;
int m;
//Calling binary_search function with parameters and taking result back
bool retVal=binary_search(v,value,m);
if(retVal==true)
{
cout<<"Found. m="<<m<<endl;
}
else{
cout<<"Not found. m="<<m<<endl;
}
cout<<"Continue(y/n)?";
cin>>choice;
}while(choice=='y'); //Loop till choice is 'y'
//Closing file connection
myfile.close();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.