Add binary_search() (page 462) to your program. Modify main() to prompt the user

Question

Add binary_search() (page 462) to your program. Modify main() to prompt the user for a number to search (until ^D) and display the position of the number in the sorted vector. Try your program for the following user input:

The output should be:

int binary_search(vector<int> v, int from, int to, int value)
{
if (from > to)
return -1;
int mid = (from + to) / 2;
if (v[mid] == value)
return mid;
else if (v[mid] < value)
return binary_search(v, mid + 1, to, value);
else
return binary_search(v, from, mid - 1, value);
}

#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
//selection sort function prototype
void selectionSort(vector<int>&v);
//Main method
int main()
{
   //file read object
   ifstream file;
   //vector declaration
   vector<int>numbers;
   //name of the filr given the object to open
   file.open("sort.txt");
   //file is not found error
   if (!file) {
       cout << "File not found" << endl;
       return 0;
   }
   //Other wise read file data and store in a vector
   else {
       while (!file.eof()) {
           int line;
           if (file >> line){
               numbers.push_back(line);
           }

       }
       //Vector values before sort
       cout << "Before sorting:" << endl;
       for (int i = 0; i < numbers.size(); i++) {
           cout << numbers[i] << " ";
       }

       cout << endl;
   }
   //call sort function
   selectionSort(numbers);
   cout << "After sorting:" << endl;
   //Vector values after sort
   for (int i = 0; i < numbers.size(); i++) {
       cout << numbers[i] << " ";
   }

   cout << endl;

    return 0;
}
//Selection sort implementation
void selectionSort(vector<int> &v) {
   int vecsize = v.size();
   for (int i = 0; i < vecsize-1; i++)
       for (int j = i + 1; j < vecsize; j++)
           if (v[i] > v[j])
               swap(v[i], v[j]);
}

  1  15  18  40  30  50  ^D 

Explanation / Answer

#include<iostream>

#include<fstream>

#include<vector>

#include <string>

using namespace std;

//selection sort function prototype

void selectionSort(vector<int>&v);

int binary_search(vector<int> v, int from, int to, int value) {

if (from > to)

return -1;

int mid = (from + to) / 2;

if (v[mid] == value)

return mid;

else if (v[mid] < value)

return binary_search(v, mid + 1, to, value);

else

return binary_search(v, from, mid - 1, value);

}

//Main method

int main()

{

//file read object

ifstream file;

//vector declaration

vector<int>numbers;

//name of the filr given the object to open

file.open("sort.txt");

//file is not found error

if (!file) {

cout << "File not found" << endl;

return 0;

}

//Other wise read file data and store in a vector

else {

while (!file.eof()) {

int line;

if (file >> line){

numbers.push_back(line);

}

}

//Vector values before sort

cout << "Before sorting:" << endl;

for (int i = 0; i < numbers.size(); i++) {

cout << numbers[i] << " ";

}

cout << endl;

}

//call sort function

selectionSort(numbers);

cout << "After sorting:" << endl;

//Vector values after sort

for (int i = 0; i < numbers.size(); i++) {

cout << numbers[i] << " ";

}

cout << endl;

string elem;

while(1) {

cout << "Enter a number to be searched in the vector (^D to stop) : ";

cin >> elem;

if(elem == "^D")

break;

int pos = binary_search(numbers, 0, numbers.size()-1, stoi(elem));

cout << pos;

cout << endl;

}

return 0;

}

//Selection sort implementation

void selectionSort(vector<int> &v) {

int vecsize = v.size();

for (int i = 0; i < vecsize-1; i++)

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

if (v[i] > v[j])

swap(v[i], v[j]);

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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