Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 05-04-2003
volk
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.
• 05-04-2003
alpha
I think you can. You might want to check, but the > , < , <=, and >= are overloaded for strings.
• 05-04-2003
volk
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; }```
• 05-04-2003
Hammer
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.

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); }```
Now, to get a line of text, use getline like this:

>>getline (cin, name[i]);
• 05-04-2003
alpha
try making found a bool (in sort)
• 05-04-2003
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?
• 05-04-2003
Hammer
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?
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.

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; }```
• 05-05-2003
CornedBee
Try the sort and search functions from <algorithm> and you'll see that it works.
• 05-05-2003
volk
There are search and sort functions in some header file called <algorithm>?
• 05-05-2003
volk
Why won't this code work if a binary search works fine on strings?

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; }```
How do you use the functions from <algorithm>? Maybe that's the answer.
• 05-05-2003
CornedBee
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"));```
• 05-05-2003
ripper079
Quote:

There are search and sort functions in some header file called <algorithm>?
Yes

Quote:

How do you use the functions from <algorithm>? Maybe that's the answer.
Like this
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; }```
• 05-05-2003
hk_mp5kpdw
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.
• 05-05-2003
CornedBee
Very true, and probably the best solution.
• 05-05-2003
volk
Thanks for the algorithms, people! Anyway, no one told me what was wrong with the code I posted.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last