Your company has been researching ways to improve the efficiency the mobile devi

Question

Your company has been researching ways to improve the efficiency the mobile devices that it produces. Your group is tasked with finding a way to reduce media retrieval time from a playlist that is in alphabetical order. Your Algorithm Group has recently been reviewing the divide-and-conquer paradigm and has decided to test a divide and conquer approach.

Assignment

Part 1

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 into 2 sublists during each step; however, for your assignment, you will build and algorithm that splits the list into 3 sublists during each step.

Part 2

What is the time complexity (in Big-O notation) of your algorithm with respect to the size of the playlist?  

How does this time complexity compare to the time complexity of binary search (in terms of Big-O)?

Note: It would be great if your answer follows APA style standards

Explanation / Answer

Part 1)

#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'));
}

Part 2)

The algorithm takes O(n^2) time since there is a for loop inside a while loop for this code.

However, using binary search might decrease the time complexity to O(n) or O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.