Search an array in three subsections for a specified song

  • Comp Sci
  • Thread starter richworldinc
  • Start date
  • Tags
    Array Search
In summary, the function mySearch searches through a song title and index into an array of strings to find the song the user is looking for.
  • #1
richworldinc
5
1
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++)
{
cout << 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;
cout << "enter a song title: " << endl;
getline(cin, songTitle);
cout << endl;
cout << "locating: " + songTitle << endl;
int songIndex = mySearch(songArray, arraySize, songTitle, songIndex);
cout << endl;
cout << "the index for" << songTitle << " is " << songIndex << 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');
}
 
Physics news on Phys.org
  • #2
You need to repost you code in "code" tags so the forum software doesn't interpret
Code: 
[i]
as an italics tag and strip it.
 
  • Like
Likes berkeman
  • #3
C++: 
#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;
    songIndex = -1;

    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
    {
        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;
        cout << "enter a song title: " << endl;
        getline(cin, songTitle);
        cout << endl;
        cout << "locating: " + songTitle << endl;
        int songIndex = mySearch(songArray, arraySize, songTitle, songIndex);
        cout << endl;
        cout << "the index for" << songTitle << " is " << songIndex << 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');
}
 
  • Like
Likes berkeman
  • #4
richworldinc said:
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.
C++: 
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.
C++: 
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.
 
  • #5
Code: 
#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
 
Last edited by a moderator:
  • #6
richworldinc said:
i have having trouble tyring to figure out what lines to use
What do you mean by "what lines to use"?
 
  • #7
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
 
  • #8
richworldinc said:
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.
richworldinc said:
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?
 

1. How do I search for a specific song in an array with three subsections?

To search for a specific song in an array with three subsections, you can use a loop to iterate through each subsection and use a conditional statement to check if the song matches the specified song. If a match is found, the loop can be terminated and the index of the song can be returned.

2. What is the time complexity of searching for a song in an array with three subsections?

The time complexity of searching for a song in an array with three subsections is O(n), where n is the number of elements in the array. This is because the algorithm needs to iterate through each element in the array to find a match, and the number of iterations will increase linearly with the size of the array.

3. Can I use a binary search algorithm to search for a song in an array with three subsections?

No, a binary search algorithm cannot be used to search for a song in an array with three subsections. This is because a binary search algorithm requires the array to be sorted, and dividing the array into three subsections would disrupt the sorting order.

4. How can I improve the efficiency of searching for a song in an array with three subsections?

One way to improve the efficiency of searching for a song in an array with three subsections is to use a hash table. By storing the songs and their corresponding indices in a hash table, the search time can be reduced to O(1) on average. Another way is to use a binary search tree, which would have a time complexity of O(log n) for searching, but would require the array to be sorted.

5. What happens if the specified song is not found in the array with three subsections?

If the specified song is not found in the array with three subsections, the search algorithm will iterate through the entire array and return a null or -1 value to indicate that the song was not found. It is important to handle this case in the code to avoid any errors or unexpected behavior.

Similar threads

Comp Sci C++ search algorithm with 3 sublists
    • Engineering and Comp Sci Homework Help
Replies
17
Views
5K
Trying to override the hashcode()
    • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
Comp Sci Keypad Translation Solution: Program for Correctly Mapping Keys to Letters
    • Engineering and Comp Sci Homework Help
Replies
24
Views
2K
Comp Sci How Does a Boolean Variable Impact Program Functionality in C++?
    • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
Jumble Word Game with Point Tracker: A Fun Way to Practice Coding
    • Engineering and Comp Sci Homework Help
Replies
8
Views
1K
Comp Sci I'm not understanding Parameterized Constructors in C++
    • Engineering and Comp Sci Homework Help
Replies
2
Views
944
Comp Sci Searching Array for an Element using Linear Search
    • Engineering and Comp Sci Homework Help
Replies
4
Views
927
Program Bug: Programming Class
    • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
Comp Sci Problem with C++ Information Structures, Pointers, Arrays
    • Engineering and Comp Sci Homework Help
Replies
3
Views
2K
Character pattern program -- Print large words using "X" characters
    • Programming and Computer Science
Replies
12
Views
1K

Hot Threads

Recent Insights

Back
Top