Is it possible to use a binary search on an array of strings, or does that only work with numbers? I'm guessing you'd have to completely change the binary search algorithm if you want it to work with strings.
Printable View
Is it possible to use a binary search on an array of strings, or does that only work with numbers? I'm guessing you'd have to completely change the binary search algorithm if you want it to work with strings.
I think you can. You might want to check, but the > , < , <=, and >= are overloaded for strings.
Well, this code sure doesn't work:
Code:#include <iostream>
#include <string>
using namespace std;
void sort (string names[], int size);
int search(string names[], int size, string value);
int main()
{
string names [] = {"hi", "hello", "how are you"};
string name[33];
int results;
sort(names, 3);
cout << "Enter a string to search for" << endl;
cin.getline(name, 33);
while ((results = search(names, 3, name)) == -1)
{
cout << "Your string was not found" << endl;
cin.getline(name, 33);
}
cout << "Your string was found" << endl;
return 0;
}
void sort (string names[], int size)
{
string hold;
int finish;
do
{
finish = 0;
for (int i = 0; i < size - 1; i++)
{
if (string[i] > string[i + 1])
{
hold = string[i];
string[i] = string[i + 1];
string[i + 1] = hold;
finish = 1;
}
}
}while (finish != 0)
}
int search(string names[], int size, string value)
{
int first = 0;
int middle;
int last = size - 1;
int position = -1;
int found = 0;
while (!found && first <= last)
{
middle = (first + last) / 2;
if (names[middle] == value)
{
found = 1;
position = middle;
}
else if (names[middle] > value)
last = middle - 1;
else
first = middle + 1;
}
return position;
}
I think you need to work on sections of your program at a time. The sort function doesn't work, so I've stripped that bit out, and made something that will at least compile.
Now, to get a line of text, use getline like this:Code:#include <iostream>
#include <string>
using namespace std;
void sort (string names[], int size);
int main()
{
string names [] = {"hi", "hello", "how are you"};
sort(names, 3);
for (int i =0; i < 3; i++)
cout <<names[i] <<endl;
return 0;
}
void sort (string names[], int size)
{
string hold;
int finish;
do
{
finish = 0;
for (int i = 0; i < size - 1; i++)
{
if (names[i] > names[i + 1])
{
hold = names[i];
names[i] = names[i + 1];
names[i + 1] = hold;
finish = 1;
}
}
}while (finish != 0);
}
>>getline (cin, name[i]);
try making found a bool (in sort)
So it's not possible to search strings? I guess that's why Hammer took out the search function. So a binary search is made specifically for numbers, right?
I took it out to simplify the program as the sort() function was wrong. Like I said, get one bit working first, then move on to the next.Quote:
Originally posted by volk
So it's not possible to search strings? I guess that's why Hammer took out the search function. So a binary search is made specifically for numbers, right?
As for binary searches, they'll work on strings just fine. Here's another version of main to replace that in your original post.
Code:int main()
{
string names [] = {"hi", "hello", "how are you"};
string name;
int results;
sort(names, 3);
cout << "Enter a string to search for" << endl;
getline(cin, name);
while ((results = search(names, 3, name)) == -1)
{
cout << "Your string was not found" << endl;
getline(cin, name);
}
cout << "Your string was found" << endl;
return 0;
}
Try the sort and search functions from <algorithm> and you'll see that it works.
There are search and sort functions in some header file called <algorithm>?
Why won't this code work if a binary search works fine on strings?
How do you use the functions from <algorithm>? Maybe that's the answer.Code:#include <iostream>
#include <string>
using namespace std;
void sort (string names[], int size);
int search(string names[], int size, string value);
int main()
{
string names [] = {"hi", "hello", "how are you"};
string name[33];
int results;
sort(names, 3);
cout << "Enter a string to search for" << endl;
getline(cin, name);
while ((results = search(names, 3, name)) == -1)
{
cout << "Your string was not found" << endl;
getline(cin, name);
}
cout << "Your string was found" << endl;
return 0;
}
void sort (string names[], int size)
{
string hold;
int finish;
do
{
finish = 0;
for (int i = 0; i < size - 1; i++)
{
if (names[i] > names[i + 1])
{
hold = names[i];
names[i] = names[i + 1];
names[i + 1] = hold;
finish = 1;
}
}
}while (finish != 0);
}
int search(string names[], int size, string value)
{
int first = 0;
int middle;
int last = size - 1;
int position = -1;
int found = 0;
while (!found && first <= last)
{
middle = (first + last) / 2;
if (names[middle] == value)
{
found = 1;
position = middle;
}
else if (names[middle] > value)
last = middle - 1;
else
first = middle + 1;
}
return position;
}
Code:#include <algorithm>
string names [] = {"hi", "hello", "how are you"};
std::sort(names, names+3);
bool is_in_there = std::binary_find(names, names+3, string("hi"));
YesQuote:
There are search and sort functions in some header file called <algorithm>?
Like thisQuote:
How do you use the functions from <algorithm>? Maybe that's the answer.
Code:#include <iostream>
#include <string>
#include <algorithm>
#include <conio.h>
#include <vector>
using namespace std;
int main()
{
vector<string> names;
names.push_back("Daniel");
names.push_back("Eric");
names.push_back("Bill");
names.push_back("Joseph");
names.push_back("Alex");
cout << "Unsorted array" << endl << endl;;
for (vector<string>::iterator start = names.begin(); start != names.end(); ++start)
cout << "Name : " << *start << endl;
cout << endl;
/* Sort vector*/
sort(names.begin(), names.end());
cout << "Sorted vector array" << endl << endl;
for (vector<string>::iterator start = names.begin(); start != names.end(); ++start)
cout << "Name : " << *start << endl;
cout << endl;
string NameToSearch("Eric");
/* Search for a name */
vector<string>::iterator findaName = find(names.begin(), names.end(), NameToSearch);
if (findaName != names.end())
cout << "Found name: " << *findaName << endl;
else
cout << "Sorry no match" << endl;
getch();
return 0;
}
As a side note, the string elements could be stored in a set or multiset container. Typical implementations of this type of container store these elements as a balanced binary tree. You can then use the member functions, find() for example, to search for elements in the set.
Very true, and probably the best solution.
Thanks for the algorithms, people! Anyway, no one told me what was wrong with the code I posted.