Question

Write a version of the binary search algorithm that can be used to search a string vector object. Also, write a program to test your algorithm. (Use the selection sort algorithm you developed in Programming Exercise 12 to sort the vector.) Your program should prompt the user to input a series of strings, ending the input stream with zzz. The program should then prompt the user to search for a specific string in the list. If the string is found in the list:

 x is found in the list

else:

x is not in the list

*need answer in C++*

Answer 1

Algorithm

Algorithm: BinarySearch(vector<string> vs, string x)
1. Set I = 0, J = vs.size()
2. Repeat while I<=J do
3. Set Mid = (INT)((I+J)/2)
4. If  vs[mid]==x Then Goto step 6
5. If vs[mid] > x Then Set J = Mid -1
     Else Set I = Mid + 1
[End of loop]
6. If I<=J Then
       Print x + " is found in the list"
   Else
      Print x + " is not in the list"
7. Return

Program

#include <iostream>
#include <vector>
using namespace std;

//main function
int main()
{
vector<string> vs;
string st;
//prompt the user to input a series of strings
while(1)
{
cout<<"Enter a string (enter zzz to end) :";
cin >> st;
if(st=="zzz")
break;
vs.push_back(st);
}

//selection sort the list
for(int i=0; i<vs.size()-1; i++)
{
int k = i;
for(int j=i+1; j<vs.size(); j++)
{
if(vs[k]>vs[j])
k = j;
}
st = vs[i];
vs[i] = vs[k];
vs[k] = st;
}
//display the sorted list
for(int i=0; i<vs.size(); i++)
{
cout<<vs[i]<<" ";
}
cout<<endl;

// prompt the user to search for a specific string in the list.
cout<<"Enter a string to search: ";
cin >> st;

int i=0, j=vs.size()-1, mid;
//binary search
while(i<=j)
{
mid = (i+j)/2;
if(vs[mid]==st)
break;
if(vs[mid]>st)
j = mid-1;
else
i = mid+1;
}
if(i<=j)
cout<<st<<" is found in the list"<<endl;
else
cout<<st<<" is not in the list"<<endl;

return 0;
}

Output: