# C++ search algorithm with 3 sublists

• Comp Sci

## Homework Statement

This is the assignment instructions:[/B]
• 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.
• This searching algorithm will employ a divide-and-conquer approach similar to that in binary search, but with a slight variation. In binary search, a list is split in 2 sublists during each step; however, for your assignment, you will build and algorithm that splits the list into 3 sublists during each step.

## Homework Equations

I am VERY VERY new to C++. I have been searching online for several hours now and need help splitting the array into 3 sublists and then searching those 3 lists for the user input. In the following code, I initialize the array with 21 songs, take user input for the search string, and then output the search string and the array being searched so the user can verify whether the search string actually does or does not exist in the songArray.

I need help with the next two steps:
step 1:
Split the array into 3 sublists
step 2:
Search the sublists

## The Attempt at a Solution

Code:
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
string songName;
string songArray[] = {"Against the Wind", "Bohemian Rhapsody", "California Love", "(Don't Fear) The Reaper", "Facade", "Hello", "I Fought the Law", "Iron Man", "King Nothing", "Knocking On Heaven's Door", "Livin' On a Prayer", "Love Story", "Macarena", "No Particular Place to Go", "On Top of the World", "Party Rock Anthem", "Piano Man", "Pink", "She Talks to Angels", "The Twist", "You Give Love a Bad Name"};

cout << "Please Enter A Song Name..." << endl;
getline (cin, songName);
cout << endl;

cout << "Searching for: " + songName << endl << endl;

for (int i = 0; i < sizeof(songArray)/sizeof(string); i++){
cout << songArray[i] << endl;
}

// split array into 3 sublists and search these lists for songName
// if song exists return index,
// else return -1
return 0;
}

Last edited by a moderator:

Mark44
Mentor

## Homework Statement

This is the assignment instructions:[/B]
• 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.
• This searching algorithm will employ a divide-and-conquer approach similar to that in binary search, but with a slight variation. In binary search, a list is split in 2 sublists during each step; however, for your assignment, you will build and algorithm that splits the list into 3 sublists during each step.

## Homework Equations

I am VERY VERY new to C++. I have been searching online for several hours now and need help splitting the array into 3 sublists and then searching those 3 lists for the user input. In the following code, I initialize the array with 21 songs, take user input for the search string, and then output the search string and the array being searched so the user can verify whether the search string actually does or does not exist in the songArray.

I need help with the next two steps:
step 1:
Split the array into 3 sublists
step 2:
Search the sublists

## The Attempt at a Solution

Code:
#include <iostream>
#include <string>
using namespace std;

int main(int argc, char** argv) {
string songName;
string songArray[] = {"Against the Wind", "Bohemian Rhapsody", "California Love", "(Don't Fear) The Reaper", "Facade", "Hello", "I Fought the Law", "Iron Man", "King Nothing", "Knocking On Heaven's Door", "Livin' On a Prayer", "Love Story", "Macarena", "No Particular Place to Go", "On Top of the World", "Party Rock Anthem", "Piano Man", "Pink", "She Talks to Angels", "The Twist", "You Give Love a Bad Name"};

cout << "Please Enter A Song Name..." << endl;
getline (cin, songName);
cout << endl;

cout << "Searching for: " + songName << endl << endl;

for (int i = 0; i < sizeof(songArray)/sizeof(string); i++){
cout << songArray[i] << endl;
}

// split array into 3 sublists and search these lists for songName
// if song exists return index,
// else return -1
return 0;
}
I think that the intention here in splitting into three sublists is to determine the number of strings in the array of strings, and then simply divide it into thirds. So if there are 30 strings in the array, the first subarray will be at indexes 0 through 9, the next will be at indexes 10 through 19, and the last will be at indexes 20 through 29. If the number of strings in the array isn't evenly divisible by 3, then the subarrays won't be exactly the same in size.

Also, you should write a function to do the search, rather than have everything in your main() function. The parameters to the search function should be the address of the array, the size (number of elements) of the array, the address of the string to search for, and the size in bytes of this string.

This type of search is very similar to a binary search, but instead of splitting the array into two parts (binary), you're splitting the array into three parts (ternary or trinary). Also, like a binary search, your function should almost certainly be recursive.

Hi Mark,

To start, I moved all of the search code into a search function as advised... *SEE CODE BELOW*

Code:
#include <iostream>
#include <string>
using namespace std;

string songName;
string songArray[] = {"Against the Wind", "Bohemian Rhapsody", "California Love", "(Don't Fear) The Reaper", "Facade", "Hello", "I Fought the Law", "Iron Man", "King Nothing", "Knocking On Heaven's Door", "Livin' On a Prayer", "Love Story", "Macarena", "No Particular Place to Go", "On Top of the World", "Party Rock Anthem", "Piano Man", "Pink", "She Talks to Angels", "The Twist", "You Give Love a Bad Name"};

void searchForSongs(){
cout << "Searching for: " + songName << endl << endl;

for (int i = 0; i < sizeof(songArray)/sizeof(string); i++){
cout << songArray[i] << endl;
}

// split array into 3 sublists and search these lists for songName
// if song exists return index,
// else return -1
}

int main(int argc, char** argv) {

cout << "Please Enter A Song Name..." << endl;
getline (cin, songName);
cout << endl;

searchForSongs();

}

As for this:
Also, like a binary search, your function should almost certainly be recursive.
You are correct, it should be recursive...

However, I still can't figure out how to split the original array into 3 sublists...

Ok, so I have made a bit more progress, but I'm getting stuck on splitting the array still, can anyone point me to the next step?

Code:
#include <iostream>
#include <string>
using namespace std;

string songName;
string songArray[] = {"Against the Wind", "Bohemian Rhapsody", "California Love", "(Don't Fear) The Reaper", "Facade", "Hello", "I Fought the Law", "Iron Man", "King Nothing", "Knocking On Heaven's Door", "Livin' On a Prayer", "Love Story", "Macarena", "No Particular Place to Go", "On Top of the World", "Party Rock Anthem", "Piano Man", "Pink", "She Talks to Angels", "The Twist", "You Give Love a Bad Name"};

void searchForSongs(){
cout << "Searching for: " + songName << endl << endl;

for (int i = 0; i < sizeof(songArray)/sizeof(string); i++){
cout << songArray[i] << endl;
}

// Split array
int sizeToSplit = (sizeof(songArray)/sizeof(string))/3; // Size of new arrays
int arrayLength = sizeof(songArray)/sizeof(string);

for (int i = 0; i < arrayLength; i = i + sizeToSplit)
{
string val[sizeToSplit] = {};

if (arrayLength < i + sizeToSplit)
{
sizeToSplit = arrayLength - i;
//create new array
//push data to new array(s)
}
}
}

int main(int argc, char** argv) {

cout << "Please Enter A Song Name..." << endl;
getline (cin, songName);
cout << endl;

searchForSongs();

}

Mark44
Mentor
Your search function should have parameters and should be recursive. It should not be using global variables.

Here's how I see the prototype for this function, for starters.
C:
int searchForSongs(string songArray[], int arraySize, string searchTarget, int targetSize)

If the target string is found, the function returns 1. If the target string is not found, splits the array of strings into three subarrays, and calls itself recursively on each subarray. When each subarray consists of one string, the function will either find the target string in one of the subarrays (and return 1) or won't find the target string at all (and returns 0).

I haven't written any code for this, but the above is how I would approach this problem.

If you have an array, how do you find out how many elements are in the array?

Your search function should have parameters and should be recursive. It should not be using global variables.

Here's how I see the prototype for this function, for starters.
C:
int searchForSongs(string songArray[], int arraySize, string searchTarget, int targetSize)

If the target string is found, the function returns 1. If the target string is not found, splits the array of strings into three subarrays, and calls itself recursively on each subarray. When each subarray consists of one string, the function will either find the target string in one of the subarrays (and return 1) or won't find the target string at all (and returns 0).

I haven't written any code for this, but the above is how I would approach this problem.

If you have an array, how do you find out how many elements are in the array?
The following code returns the number of elements in my song array:
C:
sizeof(songArray)/sizeof(string); // Size of the array / size of each element gives the actual size of the array.

Thanks for the pointer, I will keep trying to move forward from here.

The following code returns the number of elements in my song array:
C:
sizeof(songArray)/sizeof(string); // Size of the array / size of each element gives the actual size of the array.

Thanks for the pointer, I will keep trying to move forward from here.
Your search function should have parameters and should be recursive. It should not be using global variables.

Here's how I see the prototype for this function, for starters.
C:
int searchForSongs(string songArray[], int arraySize, string searchTarget, int targetSize)

If the target string is found, the function returns 1. If the target string is not found, splits the array of strings into three subarrays, and calls itself recursively on each subarray. When each subarray consists of one string, the function will either find the target string in one of the subarrays (and return 1) or won't find the target string at all (and returns 0).

I haven't written any code for this, but the above is how I would approach this problem.

If you have an array, how do you find out how many elements are in the array?

Ok, got rid of the globals, and am now passing everything as params, I will continue to work on this as we go, now to actually splitting the arrays...I am honestly a bit confused about recursion here, but will continue to try to move forward...
NEW CODE:
Code:
#include <iostream>
#include <string>
using namespace std;

int searchForSongs(string songArray[], int arraySize, string songName, int targetSize){

for (int i = 0; i < arraySize; i++){
cout << songArray[i] << endl;
}
//Split array here

}

int main(int argc, char** argv) {

string songArray[] = {"Against the Wind", "Bohemian Rhapsody", "California Love", "(Don't Fear) The Reaper", "Facade", "Hello", "I Fought the Law", "Iron Man", "King Nothing", "Knocking On Heaven's Door", "Livin' On a Prayer", "Love Story", "Macarena", "No Particular Place to Go", "On Top of the World", "Party Rock Anthem", "Piano Man", "Pink", "She Talks to Angels", "The Twist", "You Give Love a Bad Name"};
int targetSize = (sizeof(songArray)/sizeof(string))/3; // Size of new arrays
int arraySize = sizeof(songArray)/sizeof(string);
string songName;

cout << "Please Enter A Song Name..." << endl;
getline (cin, songName);
cout << endl;
cout << "Searching for: " + songName << endl << endl;

searchForSongs(songArray, arraySize, songName, targetSize);

}

Moving forward I will only post the code for the searchForSongs function as everything seems to be right to this point:

Code:
int searchForSongs(string songArray[], int arraySize, string songName, int targetSize){

for (int i = 0; i < arraySize; i++){
cout << songArray[i] << endl;
}
//Split array into 3 sublists here (STILL DON'T KNOW HOW TO SPLIT ARRAY...)

if(!songName)
{
searchForSongs(songArray, arraySize, songName, targetSize);
}
else
{
return songArray[songName];
}
}

Mark44
Mentor
Moving forward I will only post the code for the searchForSongs function as everything seems to be right to this point:

Code:
int searchForSongs(string songArray[], int arraySize, string songName, int targetSize){

for (int i = 0; i < arraySize; i++){
cout << songArray[i] << endl;
}
//Split array into 3 sublists here (STILL DON'T KNOW HOW TO SPLIT ARRAY...)

if(!songName)
{
searchForSongs(songArray, arraySize, songName, targetSize);
}
else
{
return songArray[songName];
}
}
arraySize is the number of elements in the songArray array.
Set bound1 = arraySize / 3
Set bound2 = bound1 + arraySize / 3
First third: songArray[0] through songArray[bound1 - 1]
Second third: songArray[bound1] through songArray[bound2 - 1]
Last third: songArray[bound2] through songArray[arraySize - 1]

Note that integer division is intended here.
The three parts will have equal numbers of elements in them if arraySize is evenly divisible by 3. Otherwise the last part will have one or two extra elements.

Update on requirements... Algorithm must be non-recursive...
I feel like I am almost there, but I am still misunderstanding something about writing the search part of the algorithm. I have included my updated code. Now all it does is continually print the first song in the array infinitely, please advise??

Code:
#include <iostream>
#include <string>
using namespace std;

int mySearch(string songArray[], int arraySize, string songName, int songIndex){

for (int i = 0; i < arraySize; i+1){
cout << songArray[i] << endl;  // Print Out Array to verify if value exists
}

int searchBegin = 0;
int searchEnd = arraySize - 1;
int pos1 = searchBegin + (searchEnd-searchBegin+1)/3;
int pos2 = searchBegin + 2*(searchEnd-searchBegin+1)/3;
songIndex = -1; // the initial value

while(searchBegin < searchEnd && songIndex != -1){
if (songArray[pos1] == songName)
{
songIndex = pos1;
}
else if (songArray[pos1] < songName)
{
searchBegin = searchBegin - 1;
searchEnd = searchEnd - 1;
}
else if (songArray[pos2] == songName)
{
songIndex = pos2;
}
else
{
searchBegin = searchBegin + 1;
searchEnd = searchEnd + 1;

if(songArray[pos2] == songName)
{
songIndex = pos2;
}
}
return songIndex;
}

}

int main(int argc, char** argv) {

string songArray[] = {"Against the Wind", "Bohemian Rhapsody", "California Love", "(Don't Fear) The Reaper", "Facade", "Hello", "I Fought the Law", "Iron Man", "King Nothing", "Knocking On Heaven's Door", "Livin' On a Prayer", "Love Story", "Macarena", "No Particular Place to Go", "On Top of the World", "Party Rock Anthem", "Piano Man", "Pink", "She Talks to Angels", "The Twist", "You Give Love a Bad Name"};
int arraySize = sizeof(songArray)/sizeof(string);
string songName;

cout << "Please Enter A Song Name..." << endl;
getline (cin, songName);
cout << endl;
cout << "Searching for: " + songName << endl << endl;

int songIndex = mySearch(songArray, arraySize, songName, songIndex);
cout << "Index for song " << songName << " is " << songIndex << endl;

}

Mark44
Mentor
OK, I think I understand where this is supposed to go.
After dividing the song list into thirds, look at the first sublist. Compare the target song with the beginning and ending songs of that sublist. If the target song is "between" the first and last songs in that sublist, search through that sublist for the song. If it's found, return the index of the found song. If it can't be found in that sublist, return whatever you're supposed to return when the target song isn't in the list.

If the target song isn't in the first sublist (because it is "greater" than the last song in the first sublist), look in the second sublist, and compare the target song to the first and last songs of that sublist, carrying on exactly as described above.

If the target song isn't in the second sublist (because it is "greater" than the last song in the second sublist), look in the last sublist, and compare the target song to the first and last songs in the third sublist, exactly as before.

This algorithm works because the assumption is that the large list is sorted in alphabetical order, so the three parts will also be sorted in this order. If the target song isn't in a given sublist, you only need to check the first and last songs in the sublist to determine that the target song isn't there. Once you find a sublist that the song could potentially be in, then you need to check it against each song in the sublist, but you will have reduced the search time by roughly a factor of three.

new code still just returns the first array item infinitely, any pointers Mark?

Code:
#include <iostream>
#include <string>
using namespace std;

int mySearch(string songArray[], int arraySize, string songName, int songIndex){

for (int i = 0; i < arraySize; i+1){
cout << songArray[i] << endl;  // Print Out Array to verify if value exists
}

int searchBegin = 0;
int searchEnd = arraySize - 1;
int pos1 = searchBegin + (searchEnd-searchBegin+1)/3;
int pos2 = searchBegin + 2*(searchEnd-searchBegin+1)/3;
songIndex = -1; // the initial value

while((searchBegin <= searchEnd) && (songIndex == -1)){
if (songArray[pos1] == songName)
{
songIndex = pos1;
return songIndex;
}
else if (songArray[pos1] < songName)
{
searchEnd = pos1 - 1;
}
else if (songArray[pos2] == songName)
{
songIndex = pos2;
return songIndex;
}
else if(songArray[pos2] < songName)
{
searchBegin = pos2+1;

}
else if((songArray[pos1] < songName)&& (songArray[pos2] > songName))
{
searchBegin = pos1 + 1;
searchEnd = pos2 - 1;
}
else{
songIndex = -1;
return songIndex;
}

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

}
return songIndex;
}

int main(int argc, char** argv) {

string songArray[] = {"Against the Wind", "Bohemian Rhapsody", "California Love", "(Don't Fear) The Reaper", "Facade", "Hello", "I Fought the Law", "Iron Man", "King Nothing", "Knocking On Heaven's Door", "Livin' On a Prayer", "Love Story", "Macarena", "No Particular Place to Go", "On Top of the World", "Party Rock Anthem", "Piano Man", "Pink", "She Talks to Angels", "The Twist", "You Give Love a Bad Name"};
int arraySize = sizeof(songArray)/sizeof(string);
string songName;

cout << "Please Enter A Song Name..." << endl;
getline (cin, songName);
cout << endl;
cout << "Searching for: " + songName << endl << endl;

int songIndex = mySearch(songArray, arraySize, songName, songIndex);
cout << "Index for song " << songName << " is " << songIndex << endl;

}

Mark44
Mentor
After a quick scan of your search routine, I don't see that you are doing what I suggested, which is:
C:
if ( (songArray[searchBegin] <= songName) && (songName < songArray[pos1]) )
{
// then target song is in the first third of the array
// compare each song in first third with target song, returning index if found
}
else if ( (songArray[pos1] <= songName) && (songName < songArray[pos2]) )
{
// similar logic for the second third of the array
}
else if ( (songArray[pos2] <= songName) && (songName < songArray[arraySize]) )
{
// similar logic for the final third of the array
}
else
{
// to get here, songName is definitely not in the array
}

BTW, are you using a debugger? If not, I would strongly advise that you start doing so.

After a quick scan of your search routine...

BTW, are you using a debugger? If not, I would strongly advise that you start doing so.

I will rewrite using your suggestions. As for the debugger, I usually do, but I have been having issues with the Dev-C++ IDE and haven't been able to get the debugger to run, which is causing me no end of trouble. Thanks so much for the continued help, I am really trying to get a handle on this and you have been an immense help.

Ok, First of all, immense thanks goes to Mark44 for helping step my way through to a solution that appears to work correctly. The code now searches and displays the proper index (working code to follow). The last step is to get the Do you wish to continue logic working. The program runs correctly the first time, but after displaying the answer, it asks the user if they would like to continue. When they say Y or y, it takes that as the songName and starts the search automatically without asking for the song name again.

Code:
#include <iostream>
#include <string>
using namespace std;

int mySearch(string songArray[], int arraySize, string songName, int songIndex){

for (int i = 0; i < arraySize; i++){
cout << i << ". " << songArray[i] << endl;  // Print Out Array to verify if value exists
}

int searchBegin = 0;
int searchEnd = arraySize - 1;
int pos1 = searchBegin + (searchEnd-searchBegin+1)/3;
int pos2 = searchBegin + 2*(searchEnd-searchBegin+1)/3;
songIndex = -1; // the initial value

while(searchBegin < searchEnd && songIndex == -1){
if ( (songArray[searchBegin] <= songName) && (songName < songArray[pos1]) )
{
for(int i = searchBegin; i < searchEnd; i++)
{
if(songArray[i] == songName)
{
songIndex = i;
return songIndex;
}
}
}
else if ( (songArray[pos1] <= songName) && (songName < songArray[pos2]) )
{
for(int i = searchBegin; i < searchEnd; i++)
{
if(songArray[i] == songName)
{
songIndex = i;
return songIndex;
}

}
}
else if ( (songArray[pos2] <= songName) && (songName < songArray[arraySize]) )
{
for(int i = searchBegin; i < searchEnd; i++)
{
if(songArray[i] == songName)
{
songIndex = i;
return songIndex;
}
}
}
else
{
songIndex = -1;
return songIndex;
}
}

}

int main(int argc, char** argv) {
char ans;
do {
string songArray[] = {"Against the Wind", "Bohemian Rhapsody", "California Love", "(Don't Fear) The Reaper", "Facade", "Hello", "I Fought the Law", "Iron Man", "King Nothing", "Knocking On Heaven's Door", "Livin' On a Prayer", "Love Story", "Macarena", "No Particular Place to Go", "On Top of the World", "Party Rock Anthem", "Piano Man", "Pink", "She Talks to Angels", "The Twist", "You Give Love a Bad Name"};
int arraySize = sizeof(songArray)/sizeof(string);
string songName;

cout << "Please Enter A Song Name..." << endl;
getline (cin, songName);
cout << endl;
cout << "Searching for: " + songName << endl << endl;
int songIndex = mySearch(songArray, arraySize, songName, songIndex);
cout << endl;
cout << "Index for song " << songName << " is " << songIndex << endl << endl;

cout << "Do you want to search again (Y/N)?" << endl;
cout << "You must type a 'Y' or an 'N' :";
cin >> ans;

} while ((ans == 'Y') || (ans == 'y'));

}

after the user enters y or Y, output is:

Index for song is -1
Do you want to search again?;

Fixed it...it seems that cin>> can leave a trailing \n character that was getting read as an enter key strike...

changing:
Code:
cout << "Do you want to search again (Y/N)?" << endl;
cout << "You must type a 'Y' or an 'N' :";
cin >> ans;

To:
Code:
cout << "Do you want to search again (Y/N)?" << endl;
cout << "You must type a 'Y' or an 'N' :";
cin >> ans;   //unobserved trailing /n acting as "enter key strike"
cin.ignore();

fixed the issue and now it works!!!!

I seem to be getting an error of songIndex saying it is not initialized yet I have checked the code to make sure it is the same multiple times

Mark44
Mentor