CODEWITHSUNDEEP
c++arrayssearchbinary-search
sircrisp
sircrisp

Reputation: 1067

Searching a array of strings

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

Upvotes: 1

Views: 9762

Answers (9)

Blastfurnace
Blastfurnace

Reputation: 18652

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?

Upvotes: 2

Dimitar Velitchkov
Dimitar Velitchkov

Reputation: 342

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").

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308206

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

Upvotes: 0

deepend0
deepend0

Reputation: 329

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;

Upvotes: 0

Roman Byshko
Roman Byshko

Reputation: 9002

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.

Upvotes: 1

jrok
jrok

Reputation: 55395

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

Upvotes: 1

Kamyar Souri
Kamyar Souri

Reputation: 1923

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

Upvotes: -1

paxdiablo
paxdiablo

Reputation: 881473

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).

Upvotes: 2

Robᵩ
Robᵩ

Reputation: 168626

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?

Upvotes: 1

Related Questions