I\'m using a binary search and I have to change it to work with strings rather t
ID: 3629226 • Letter: I
Question
I'm using a binary search and I have to change it to work with strings rather than integers. I can not write a sort routine to order the word list instead I am suppose to move the words around manually to place them in the proper order. Can you please explain step by step how to do this and explain what I have done wrong. My code is below. Thanks
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
const int NUM_NAMES = 10;
int main()
{
string names[10] = {"lisa", "tom", "zach", "heather", "ryan", "willy", "marissa", "barb", "tara", "george"};
for (int count=0; count <10; count++)
{
cout << names << endl;
}
string binarySearch(string names [], int size, char[]);
{
int first = 0,
last = names - 1,
middle,
position = -1;
bool found = false;
while (!found && first <= last)
{
middle = (first + last) / 2;
if (names[middle] == names)
{
found = true;
position = middle;
}
else if (array[middle]>names)
last = middle - 1;
else
first = middle + 1;
}
system ("pause");
return position;
}
}
Explanation / Answer
please rate - thanks
//#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
int binarySearch(string names [], int size, string name);
void sort(string[]);
const int NUM_NAMES = 10;
int main()
{
string names[10] = {"lisa", "tom", "zach", "heather", "ryan", "willy", "marissa", "barb", "tara", "george"};
string name;
cout<<"list before sorting ";
for (int count=0; count <10; count++)
{
cout << names[count] << endl;
}
cout<<"enter name to search for: ";
cin>>name;
sort(names);
cout<<"list after sorting ";
for (int count=0; count <10; count++)
{
cout << names[count] << endl;
}
int n=binarySearch(names,NUM_NAMES,name);
if(n<0)
cout<<name<<" was not found in the list ";
else
cout<<name<<" was found at location "<<n<<" of the list ";
system("pause");
}
int binarySearch(string names [], int size, string name)
{
int first = 0,
last = size - 1,
middle,
position = -1;
bool found = false;
while (!found && first <= last)
{
middle = (first + last) / 2;
if (names[middle].compare(name)==0)
{
found = true;
position = middle;
}
else if (names[middle].compare(name)>0)
last = middle - 1;
else
first = middle + 1;
}
return position;
}
void sort(string names[])
{int i,j;
string t;
for(i=0;i<NUM_NAMES-1;i++)
for(j=i;j<NUM_NAMES;j++)
if(names[i].compare(names[j])>0)
{t=names[i];
names[i]=names[j];
names[j]=t;
}
}