(3) Based on Problem P11.6 Implement a function bool binary.search (vector & v,

Question

(3) Based on Problem P11.6 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. mfollowed 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... R C:Win 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 ontinue y/n)? y Enter a value 0 ot found. m-1 ontinue y/n)? n

Explanation / Answer

#include <iostream>
#include <fstream> //for reading the file
#include <algorithm> //for sort library function
using namespace std;

bool b_search(vector <int> &v, int value, int &m){
int start = 0, ending = v.size()-1;
while(start <= ending){
int mid = start + (ending - start)/2; //to avoid overflow. This is mathematically equivalent to (start + ending)/2
if(v[mid] == value){
m = mid; //if match is found, store index in m, return true
return true;
}
else if(v[mid] > value){ //if mid element is greater than value, search in first half of the vector
ending = mid-1;
m = start; //for the case where element is not found, start will hold the value of the next larger element.
}
else{
start = mid+1; //search only in second half of the vector
m = start; //sets m to hold value of the next larger element.
}
}
return false;
}

void print(vector <int> &num, int n){ // function to print the vector elements
for(int i = 0; i < n; i++)
cout << num[i] << " ";
cout << " ";
}

int main()
{
ifstream f; //declare an input file stream variable
f.open("C:\Users\HP\Desktop\data3.txt"); // give the complete path of the file - data3.txt
if(!f) { // to check if file exists
cout << "Unable to open file";
exit(1); // terminate with error
}
vector <int> num;
int x, m;
while (f >> x) { //read the numbers from the text file like you read it from cin.
num.push_back(x); //keep adding/pushing elements to the vector
}
cout << "Before sorting: ";
int n = num.size();
print(num, n);
sort(num.begin(), num.end()); //built in function in C++ to sort a vector
cout << "After sorting: ";
print(num, n);
char ch;
do{
cout << "Enter a value: ";
cin >> x;
if(b_search(num, x, m))
cout << "Found. m = " << m << " ";
else
cout << "Not found. m = " << m << " ";
cout << "Continue (y/n) ";
cin >> ch;
}while(ch == 'y');
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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