question about strings

This is a discussion on question about strings within the C++ Programming forums, part of the General Programming Boards category; Is it possible to use a binary search on an array of strings, or does that only work with numbers? ...

  1. #1
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357

    question about strings

    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.

  2. #2
    Registered User
    Join Date
    Nov 2002
    Posts
    1,109
    I think you can. You might want to check, but the > , < , <=, and >= are overloaded for strings.

  3. #3
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357
    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;
    }

  4. #4
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    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]);
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  5. #5
    Registered User
    Join Date
    Nov 2002
    Posts
    1,109
    try making found a bool (in sort)

  6. #6
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357
    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?

  7. #7
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    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;
    }
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Try the sort and search functions from <algorithm> and you'll see that it works.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #9
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357
    There are search and sort functions in some header file called <algorithm>?

  10. #10
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357
    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.

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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"));
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #12
    Veni Vidi Vice
    Join Date
    Aug 2001
    Posts
    343
    There are search and sort functions in some header file called <algorithm>?
    Yes

    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;
    }

  13. #13
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,799
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  14. #14
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Very true, and probably the best solution.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  15. #15
    Un Artiste Extraordinaire volk's Avatar
    Join Date
    Dec 2002
    Posts
    357
    Thanks for the algorithms, people! Anyway, no one told me what was wrong with the code I posted.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question about strings in c
    By gp364481 in forum C Programming
    Replies: 9
    Last Post: 11-13-2008, 05:32 PM
  2. Question About Strings
    By spanker in forum C++ Programming
    Replies: 1
    Last Post: 07-13-2008, 05:09 AM
  3. strings question
    By cstudent in forum C Programming
    Replies: 4
    Last Post: 04-18-2008, 07:28 AM
  4. Functions and Strings Question
    By StrikeMech in forum C Programming
    Replies: 4
    Last Post: 07-18-2007, 06:07 AM
  5. Strings question
    By kimimaro in forum C Programming
    Replies: 10
    Last Post: 03-14-2005, 11:14 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21