Search an array in three subsections for a specified song

[richworldinc]

Homework Statement

In C++, code a search algorithm that searches a list of strings for a particular song. The searching algorithm will have two inputs: the playlist, which is a string array that contains a list of songs in alphabetical order; and a particular song, which is a string. If the song is found in the list, the algorithm will return the index of the song, and it will return -1 otherwise.

Relevant Equations

I took advice from another thread and tried to redo this project, but seem to be getting an error that: C4700 uninitialized local variable 'songIndex' used songs. i do not see why this produces this error

#include <iostream>
#include <string>

using namespace std;

int mySearch(string songArray[], int arraySize, string songTitle, int songIndex)
{
for (int i = 0; i < arraySize; i++)
{
count << i << "..." << songArray << endl;
}

int searchBegin = 0;
int searchEnd = 13;
int pos1 = searchBegin + (searchEnd - searchBegin + 1) / 3;
int pos2 = searchBegin + 2 * (searchEnd - searchBegin + 1) / 3;
songIndex = -1;

while (searchBegin < searchEnd && songIndex == -1)
{
if ((songArray[searchBegin] <= songTitle) && (songTitle < songArray[pos1]))
{
for (int i = searchBegin; i < searchEnd; i++)
{
if (songArray == songTitle)
{
songIndex = i;
return songIndex;
}
}
}
else if ((songArray[pos1] <= songTitle) && (songTitle < songArray[pos2]))
{
if ((songArray[searchBegin] <= songTitle) && (songTitle < songArray[pos1]))
{
for (int i = searchBegin; i < searchEnd; i++)
{
if (songArray == songTitle)
{
songIndex = i;
return songIndex;
}
}
}
}
else if ((songArray[pos2] <= songTitle) && (songTitle < songArray[arraySize]))
{
if ((songArray[searchBegin] <= songTitle) && (songTitle < songArray[pos1]))
{
for (int i = searchBegin; i < searchEnd; i++)
{
if (songArray == songTitle)
{
songIndex = i;
return songIndex;
}
}
}
}
else
{
songIndex = -1;
return songIndex;
}
}
}
int main(int argo, char** argv)
{
char ans;
do
{
string songArray[] = { "i can only imagine", "healing rain", "gods not dead", "while I am waiting", "broken", "need you now", "im not perfect", "lead me", "who you say i am", "i surrender", "10,000 reasons", "here i am to worship", "nobody" };
int arraySize = sizeof(songArray) / sizeof(string);
string songTitle;
count << "enter a song title: " << endl;
getline(cin, songTitle);
count << endl;
count << "locating: " + songTitle << endl;
int songIndex = mySearch(songArray, arraySize, songTitle, songIndex);
count << endl;
count << "the index for" << songTitle << " is " << songIndex << endl;
count << "would you like to search for another song (y/n)?" << endl;
count << "you must type 'y' or 'n'!";
cin >> ans;
cin.ignore();
} while (ans == 'y');
}

 

[pasmith]

You need to repost you code in "code" tags so the forum software doesn't interpret

[i]

as an italics tag and strip it.

 

[richworldinc]

[CODE lang="cpp" highlight="79"]#include <iostream>
#include <string>

using namespace std;

int mySearch(string songArray[], int arraySize, string songTitle, int songIndex)
{
for (int i = 0; i < arraySize; i++)
{
count << i << "..." << songArray << endl;
}

int searchBegin = 0;
int searchEnd = 13;
int pos1 = searchBegin + (searchEnd - searchBegin + 1) / 3;
int pos2 = searchBegin + 2 * (searchEnd - searchBegin + 1) / 3;
songIndex = -1;

while (searchBegin < searchEnd && songIndex == -1)
{
if ((songArray[searchBegin] <= songTitle) && (songTitle < songArray[pos1]))
{
for (int i = searchBegin; i < searchEnd; i++)
{
if (songArray == songTitle)
{
songIndex = i;
return songIndex;
}
}
}
else if ((songArray[pos1] <= songTitle) && (songTitle < songArray[pos2]))
{
if ((songArray[searchBegin] <= songTitle) && (songTitle < songArray[pos1]))
{
for (int i = searchBegin; i < searchEnd; i++)
{
if (songArray == songTitle)
{
songIndex = i;
return songIndex;
}
}
}
}
else if ((songArray[pos2] <= songTitle) && (songTitle < songArray[arraySize]))
{
if ((songArray[searchBegin] <= songTitle) && (songTitle < songArray[pos1]))
{
for (int i = searchBegin; i < searchEnd; i++)
{
if (songArray == songTitle)
{
songIndex = i;
return songIndex;
}
}
}
}
else
{
songIndex = -1;
return songIndex;
}
}
}
int main(int argo, char** argv)
{
char ans;
do
{
string songArray[] = { "i can only imagine", "healing rain", "gods not dead", "while I am waiting", "broken", "need you now", "im not perfect", "lead me", "who you say i am", "i surrender", "10,000 reasons", "here i am to worship", "nobody" };
int arraySize = sizeof(songArray) / sizeof(string);
string songTitle;
count << "enter a song title: " << endl;
getline(cin, songTitle);
count << endl;
count << "locating: " + songTitle << endl;
int songIndex = mySearch(songArray, arraySize, songTitle, songIndex);
count << endl;
count << "the index for" << songTitle << " is " << songIndex << endl;
count << "would you like to search for another song (y/n)?" << endl;
count << "you must type 'y' or 'n'!";
cin >> ans;
cin.ignore();
} while (ans == 'y');
}[/CODE]

 

[Mark44]

I took advice from another thread and tried to redo this project, but seem to be getting an error that: C4700 uninitialized local variable 'songIndex' used songs. i do not see why this produces this error

To fix this error, declare and initialize songIndex in a separate line.

int SongIndex = 0;
.
.
.
songIndex = mySearch(songArray, arraySize, songTitle, songIndex);

That's just the start of your problems though, as your code goes into an infinite loop. The logic in your mySearch() function is faulty. Here's one of the reasons why.

if ((songArray[searchBegin] <= songTitle) && (songTitle < songArray[pos1]))

In this comparison you're seeing if a given string in the array of strings is less than or equal to the string you're looking for. The actual comparison being done is a lexicographic comparison; i.e., seeing if the strings are in dictionary order. Since the strings in your array aren't in dictionary order, this comparison isn't going to work. In this sort of comparison, "cat" < "dog" and "cat" < "catch".

The best solution I can think of is to cycle through each subarray to see if a given string is equal to the search string.

 

[richworldinc]

#include <iostream>
#include <string>

using namespace std;

int mySearch(string songArray[], int arraySize, string songTitle, int songIndex)
{
    for (int i = 0; i < arraySize; i++)
    {
        cout << i << "..." << songArray[i] << endl;
    }

    int searchBegin = 0;
    int searchEnd = 13;
    int pos1 = searchBegin + (searchEnd - searchBegin + 1) / 3;
    int pos2 = searchBegin + 2 * (searchEnd - searchBegin + 1) / 3;

    while (searchBegin < searchEnd && songIndex == -1)
    {
        if ((songArray[searchBegin] <= songTitle) && (songTitle < songArray[pos1]))
        {
            for (int i = searchBegin; i < searchEnd; i++)
            {
                if (songArray[i] == songTitle)
                {
                    songIndex = i;
                    return songIndex;
                }
            }
        }
        else if ((songArray[pos1] <= songTitle) && (songTitle < songArray[pos2]))
        {
            if ((songArray[searchBegin] <= songTitle) && (songTitle < songArray[pos1]))
            {
                for (int i = searchBegin; i < searchEnd; i++)
                {
                    if (songArray[i] == songTitle)
                    {
                        songIndex = i;
                        return songIndex;
                    }
                }
            }
        }
        else if ((songArray[pos2] <= songTitle) && (songTitle < songArray[arraySize]))
        {
            if ((songArray[searchBegin] <= songTitle) && (songTitle < songArray[pos1]))
            {
                for (int i = searchBegin; i < searchEnd; i++)
                    {
                        if (songArray[i] == songTitle)
                        {
                            songIndex = i;
                            return songIndex;
                        }
                    }
            }
        }
        else
        {
            songIndex = -1;
            return songIndex;
        }
    }
}
int main(int argo, char** argv)
{
    char ans;
    do
    {
        int songIndex = -1;
        string songArray[] = {"10,000 reasons", "Broken", "God's not Dead", "Healing rain", "Here I am to worship", "I surrender", "I'm not perfect", "Lead me", "Nobody", "While I'm waiting", "Who you say I am"};
        int arraySize = sizeof(songArray) / sizeof(string);
        string songTitle;
        cout << "enter a song title: " << endl;
        getline(cin, songTitle);
        cout << endl;
        cout << "locating: " + songTitle << endl;
        int songPlace = mySearch(songArray, arraySize, songTitle, songIndex);
        cout << endl;
        cout << "the index for" << songTitle << " is " << songPlace << endl;
        cout << "would you like to search for another song (y/n)?" << endl;
        cout << "you must type 'y' or 'n'!";
        cin >> ans;
        cin.ignore();
    } while (ans == 'y');
}

this works as long i write the name exactly as it is in the code(i can deal with that)
now i have having trouble tyring to figure out what lines to use and how to find the time complexity

 

[Mark44]

i have having trouble tyring to figure out what lines to use

What do you mean by "what lines to use"?

 

[richworldinc]

I am using two int statements
one being int mysearch and the other being int main, both of them have to run to get the user input and compute the answer
I really am completely lost when trying to compute the time algorithm

 

[Mark44]

I am using two int statements
one being int mysearch and the other being int main, both of them have to run to get the user input and compute the answer

It's hard to tell what you know or don't know, based on what you wrote above. The main() function is the entry point for your program. Aside from the fact that the body of main() repeats in a loop, asking the user to enter a song title, the bulk of the work is done by the mySearch() function. To figure out the time complexity (not the time algorithm), you need to look at what mySearch() is doing.

I really am completely lost when trying to compute the time algorithm

This is pretty vague. The best I can do with such limited information is to suggest that you determine how many operations (such as comparisons) need to be done for a list of N song titles. Since you have broken the list of songs into thirds, calculating the time complexity in one part would be helpful. Also, on average (over a large number of searches, the song you're looking for will be somewhere in the middle section. This implies that an average search will have to go through the first third of song titles, and will be found about halfway through the middle third of song titles.

Do you have any worked examples of what is being asked for, like from textbook examples or class notes?