Searching a array of strings

Question

Basically the purpose of this program is to read up to 100 names from file, sort with a bubblesort, and then search for a entered name by binary search.

All seems to be working except when I enter a name that is in the list, nothing happens, I'm just prompted to enter a name again.

Say a name in the list in Elvis Presley. I am prompted to enter a name. I type in Elvis Presley. I SHOULD recieve Elvis Presley is your friend. Not happening. Any help appreciated.

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

void bubblesort(string[], const int);
void search(string[], const int);
int sub = 0;

int main()
{
 const int maxsize = 100;
 string friendArray[maxsize];

 ifstream friends;
 friends.open("myFriends.dat");

 while (sub < maxsize && getline(friends, friendArray[sub]))
   sub++;


 bubblesort(friendArray, sub);
 search(friendArray, maxsize);


 system("pause");
 return 0;
}



void bubblesort(string *array, const int size)
{
    bool swap;
    string temp;

    do
    {
        swap = false;
        for (int count = 1; count < (size - 1); count++)
        {
            if(array[count-1] >array[count])
            {
                temp = array[count-1];
                array[count-1] = array[count];
                array[count] = temp;
                swap = true;
            }
        }
    }
    while(swap);

}

void search(string *array, int size)
{
    int first = 0;
    int last = size - 1;
    int middle;
    string name;
    bool friends = false;

    do
    {
     cout<<"Please enter a name or END to terminate:";
     cin>>name;
    }
    while(!friends && first <= last && name != "END");
    {
        middle = (first + last) / 2;
        if (array[middle] == name)
            {
                friends = true;
                cout<<array[middle]<<" is my friend."<<endl;
            }
        else if (array[middle] > name)
            last = middle - 1;
        else
            last = middle + 1;
    }
}

It's not a good idea to fix the question based on the answers since it pretty much invalidates every answer and makes the question useless (since there is no problem once fixed). Unless the changes are cosmetic only, you should ask another question, deleting this one if it's no longer relevant. — paxdiablo
– paxdiablo, Commented Dec 6, 2011 at 1:31

Blastfurnace · Accepted Answer · 2011-12-06 02:20:54Z

2

In your search() function, the do { } while; { } construct is flawed. It will compile but it doesn't do what you want. I made a few changes and rearranged your code so it makes more sense.

void search(string *array, int size)
{
    string name;

    for (;;)
    {
        cout<<"Please enter a name or END to terminate:";
        getline(cin, name);
        if (name == "END") break;

        int first = 0;
        int last = size - 1;
        bool friends = false;

        while (!friends && first <= last)
        {
            int middle = (first + last) / 2;
            if (array[middle] == name)
            {
                friends = true;
                cout<<array[middle]<<" is my friend."<<endl;
            }
            else if (array[middle] > name)
                last = middle - 1;
            else
                first = middle + 1;
        }
    }
}

int main () // test the search() function
{
    string array[] = { "bird", "cat", "dog", "horse", "loon", "zebra" };
    search(array, 6);
}

SO, is this too much homework help? Should I delete this?

edited Dec 6, 2011 at 2:20

answered Dec 6, 2011 at 1:46

Blastfurnace

18.7k57 gold badges61 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

sircrisp Over a year ago

This is great, I feel I learn much better from visual examples because that is how I've learned everything so far from my book. It doesn't do a very good job at explaining the algorithms to me.

Blastfurnace Over a year ago

@sircrisp: You were close. I just rearranged your code so there is an outer loop that prompts for the search name and an inner loop that does the binary-search.

sircrisp Over a year ago

I changed my code to match yours, now after I type a name that is in the list the program does nothing but I hear my CPU fan getting louder and louder.

Blastfurnace Over a year ago

@sircrisp: Check your sorting code and make sure the array is in order before calling the search function.

Blastfurnace Over a year ago

@sircrisp: I added some testing code and this search() appears to work. The input array must be sorted in ascending order.

|

paxdiablo · Accepted Answer · 2011-12-06 01:07:40Z

2

I find it interesting that you set last in both cases where you don't find a match.

The first thing you should do is think about what that means, nudge, nudge, wink, wink :-)

You should also pass the number of used elements to search as well, rather than the size of the array (since you may not be using the full array).

answered Dec 6, 2011 at 1:07

paxdiablo

888k243 gold badges1.6k silver badges2k bronze badges

1 Comment

sircrisp Over a year ago

The two lasts was just a typo but that could have disrupted something once I have the problem I'm trying to solve solved.

Robᵩ · Accepted Answer · 2011-12-06 01:07:15Z

1

I suppose that

search(friendArray, maxsize);

should be

search(friendArray, sub);

Binary search's input condition is that the searched-in array is sorted. Your array looks like this:

Aaron Burr
Bill Cosby
Celine Dion
...
Zachary Taylor
""
""
""
""

etc.

Since an empty string is not less than a non-empty string, friendArray[0..maxsize] is not sorted, while the array friendArray[0..sub] is.

EDIT: I also just noticed that your binary search algorithm is flawed. Look again at your source material (text book, wikipedia, whatever). Isn't first supposed to be updated inside your loop?

answered Dec 6, 2011 at 1:07

Robᵩ

170k20 gold badges251 silver badges323 bronze badges

Comments

jrok · Accepted Answer · 2011-12-06 01:09:12Z

1

Operator >> reads formatted data from the stream, i.e. discards white spaces. When you say cin >> name; and enter "Elvis Presley", only "Elvis" get stored in name.

What you need is getline(cin, name);

answered Dec 6, 2011 at 1:09

jrok

55.5k10 gold badges114 silver badges146 bronze badges

1 Comment

sircrisp Over a year ago

Thanks for catching that problem still remains however.

Roman Byshko · Accepted Answer · 2011-12-06 01:13:51Z

1

Think what will happen if the length of your friends array would be 3. If I'm not mistaken there will be a problem.

Also it is recommended to use safer data types, like vector<string> for example, then you do not need to care about too much data in the input file. Also your life will get easier in the search function, since you can use iterators and do not need to pass the size of the array.

Take a look at what people say in the other answers about cin.

edited Dec 6, 2011 at 1:13

answered Dec 6, 2011 at 1:08

Roman Byshko

9,1007 gold badges39 silver badges59 bronze badges

2 Comments

sircrisp Over a year ago

I've changed cin to getline and search to search(friendArray, sub). Never used vectors before or have learned about them yet so I'd like to modify my existing code as least as possible.

Roman Byshko Over a year ago

@sircrisp Good. Think about what will happen if the length of friends is 3. I see you point, just take it as a advice and take at look at them later, it's worth it.

Dimitar Velitchkov · Accepted Answer · 2011-12-06 01:41:45Z

1

This is one do-whie loop:

do
{
 cout<<"Please enter a name or END to terminate:";
 cin>>name;
}
while(!friends && first <= last && name != "END");

The code will basically loop forever (friends will never be true and first will never be > last), prompting you for a name until you either kill the program or type in "END".

This:

{
    middle = (first + last) / 2;
    if (array[middle] == name)
        {
            friends = true;
            cout<<array[middle]<<" is my friend."<<endl;
        }
    else if (array[middle] > name)
        last = middle - 1;
    else
        last = middle + 1; 
}

will not get a chance to execute until the loop condition is false (in this case, until you type in "END").

answered Dec 6, 2011 at 1:41

Dimitar Velitchkov

3522 gold badges4 silver badges9 bronze badges

1 Comment

sircrisp Over a year ago

I changed the while to while(!friends && name != "END"); No luck though. I've been working on this for 4 hours I can't pinpoint anything anymore my logic is deaddd.

deepend0 · Accepted Answer · 2011-12-06 01:27:00Z

0

You say that all seems to be working except when you entered a name to be searched. Actually , you stepped into point.There is a mistake in your binary search code. And the first answer in this topic is toward this way.

If array is used in binary search , it must be split into two parts in each stage of search.

For example in a stage if current part is marked as follows : first - middle - last on the next stage the parts will be either between first - middle-1 or middle+1 - last.

So

    else if (array[middle] > name)
      last = middle - 1;
    else 
      last = middle + 1;

must be

  else if (array[middle] > name)
      last = middle - 1;
  else 
      first = middle + 1;

edited Dec 6, 2011 at 1:27

answered Dec 6, 2011 at 1:19

deepend0

3373 silver badges7 bronze badges

Comments

Mark Ransom · Accepted Answer · 2011-12-06 01:28:55Z

0

You have an off-by-one error in your sort.

answered Dec 6, 2011 at 1:28

Mark Ransom

310k44 gold badges423 silver badges660 bronze badges

2 Comments

sircrisp Over a year ago

Care to point out which part is wrong? I received help with the sort earlier.

Mark Ransom Over a year ago

@sircrisp, sorry this looks too much like homework for me to give the easy answer. But step through the code and see which element gets missed.

Kamyar Souri · Accepted Answer · 2011-12-06 01:08:48Z

The problem is in function search. move the } after cin>>name to the end of the function to look like:

void search(string *array, int size)
{
    int first = 0;
    int last = size - 1;
    int middle;
    string name;
    bool friends = false;

    do
    {
        cout<<"Please enter a name or END to terminate:";
        cin>>name;

        while(!friends && first <= last && name != "END");
        {
            middle = (first + last) / 2;
            if (array[middle] == name)
            {
                friends = true;
                cout<<array[middle]<<" is my friend."<<endl;
            }
            else if (array[middle] > name)
                last = middle - 1;
            else 
                last = middle + 1;
        }
    }
}

Collectives™ on Stack Overflow

Searching a array of strings

9 Answers 9

6 Comments

1 Comment

Comments

1 Comment

2 Comments

1 Comment

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

9 Answers 9

6 Comments

1 Comment

Comments

1 Comment

2 Comments

1 Comment

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related