C++ binary search with vector of objects

Question

I am writing a c++ program that is supposed to take a list of songs from a txt file and be able to shuffle, sort, and search for a song in the list. It uses a vector of objects to store the list to classify both the song and the artist. I figured out how to sort and shuffle correctly; however I'm supposed to use a binary search and that's giving me difficulty.

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstdlib>
#include <time.h>
#include <stdlib.h>
#include <random>

#include <bits/stdc++.h>
#include <algorithm>

#include "song.h"

using namespace std;

// given to you
void processFile(vector<Song> &playlist);

// you should create
void shuffle(vector<Song> &playlist);
void Sort(vector<Song> &playlist);
void displayPlaylist(vector<Song> playlist);
int binarySearch(vector<Song> &playlist, string songTitle);



int main()
{
    vector<Song> playlist;

    // sets up playlist
    processFile(playlist);

    cout << "\nInitial playlist: " << endl;

    //displayPlaylist(playlist);
    displayPlaylist(playlist);

    cout << "Welcome to the playlist display manager." << endl << endl;

    while(1)
    {
        int option;

        cout << "0. Exit" << endl;
        cout << "1. Sort Playlist" << endl;
        cout << "2. Shuffle Playlist" << endl;
        cout << "3. Search Playlist" << endl;
        cout << "Which option would you like" << endl;
        cin >> option;

        if(option == 0)
        {
            break;
        }

        else if(option == 1)
        {
            Sort(playlist);
            displayPlaylist(playlist);

        }

        else if(option == 2)
        {

        }

        else if(option == 3)
        {
            string title;
                cout << "what is the name of the song?" << endl;
                getline(cin,title);

                int songIndex = binarySearch(playlist, title);

                if(songIndex != -1)
                {
                    cout << playlist[songIndex].getTitle() << " - " << playlist[songIndex].getArtist() << endl;
                }
                else
                {

                    cout << "Couldn't find the song, sorry! :'(" << endl;
                }
        }

        else
        {
           cout << "invalid response...try again" << endl;
        }
    }

    return 0;
}

void processFile(vector<Song> &playlist)
{
    ifstream infile;
    string line;

    infile.open("songs.txt");

    if(infile.is_open())
    {
        cout << "Successful songs opening." << endl;

    }

    else
    {
        cout << "Couldn't locate file. Program closing." << endl;
        exit(EXIT_FAILURE);
    }

    while(getline(infile, line))
    {
        // first line --> song
        // second line --> artist

        if(line != "")
        {
            string song, artist;

            song = line;

            getline(infile, artist);

            Song temp(song, artist);

            playlist.push_back(temp);
        }
    }

    return;
}




int binarySearch(vector<Song> &playlist, string songTitle)
{

    Sort(playlist);

    int size;
    size = playlist.size();
    int low = 0, high = size - 1, mid;

    while(high >= low)
    {
        mid = (high + low) / 2;
        if(playlist[mid].getTitle() < songTitle)
        {
            low = mid + 1;
        }

        else if(playlist[mid].getTitle() > songTitle)
        {
            high = mid - 1;
        }

        else
        {
            return mid;
        }
    }


    return -1;
}

//sort playlist using bubble sort
void Sort(vector<Song>& playlist)
{
    int size;
    size = playlist.size();

    //iter
    for(int i= 0; i < size - 1; i++)
    {
        int smallIndex = i;
        for(int j = i + 1; j < size; j++)
        {
            //if first is less than small index then it is replaced
            if(playlist[j].getTitle() < playlist[smallIndex].getTitle())
            {
                smallIndex = j;
            }
        }
        string song, artist;

        Song temp(song, artist);
        temp = playlist[i];

        playlist[i] = playlist[smallIndex];
        playlist[smallIndex] = temp;
}
}
//display songs
void displayPlaylist(vector<Song> playlist)
{
    for(int i = 0; i < playlist.size(); i++)
    {
        cout << playlist[i].getTitle() << " - " << playlist[i].getArtist() << endl;


    }


}

Here is what my main looks like. Every time I try to choose a song to find, it just ends the program and doesn't even display the message. I am pretty new to programming so any advice would be appreciated.

_use a binary search and that's giving me difficulty_ What sort of difficulty? — 1201ProgramAlarm, Apr 05 '20 at 22:38
I mean to say I cant get it to do what I want which is verify if the song I input is in the playlist. — x-reaper, Apr 05 '20 at 22:48
Unrelated: It looks like you're getting sucked into a [cargo cult](https://en.wikipedia.org/wiki/Cargo_cult_programming) and using code without knowing what it does. `#include ` includes pretty much the entire C++ Standard Library, something you shouldn't do, making most of the other includes pointless. [Here's more reading related to bits/stdc++.h](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) so you can learn what it does and why you shouldn't use it.. — user4581301, Apr 05 '20 at 22:50
How can you tell if the song was found or not? You never do anything with the value returned by `binarySearch`. — 1201ProgramAlarm, Apr 05 '20 at 22:52
I recommend chopping the program to a small program that misbehaves exactly the way the full program does. This removes all of the ambiguity AND the reduced noise around the bug often reveals the problem to you without any further help. Use [mcve] as inspiration. — user4581301, Apr 05 '20 at 22:53

score 0 · Answer 1 · answered Apr 06 '20 at 01:13

0

As mentioned by 1201ProgramAlarm, you are not doing anything with the result of your search, try something like:

    else if(option == 3)
    {
        string title;
        cout << "what is the name of the song?" << endl;
        cin >> title;

        int songIndex = binarySearch(playlist, title);

        if(songIndex != -1)
        {
            cout << playlist[songIndex].getTitle() << " - " << playlist[songIndex].getArtist() << endl;
        }
        else
        {
            cout << "Couldn't find the song, sorry! :'(" << endl;
        }

    }

answered Apr 06 '20 at 01:13

ngdelima

1
2

I tried what you gave me and it keeps telling me the song can't be found. I took what 1201ProgramAlarm said and tried to do something similar before you showed me this and it does the same thing. I tried displaying mid to see what the integer was and it keeps coming out as -1. Do you think there's something wrong with how I set up my binary function? – x-reaper Apr 06 '20 at 17:37
Binary sesrch seems right for me. Are you sure the song you are looking for is in the playlist? I tested it with a few songs. Maybe you are having typos when looking for the song – ngdelima Apr 06 '20 at 17:40
I debugged it and I think I found the issue. I'm using songs with more than one word, and cin only takes the first word. However when I try to use getline, it doesn't ask for the users input and goes straight to the binary function. – x-reaper Apr 06 '20 at 18:23
I just edited my code to reflect the changes I made – x-reaper Apr 06 '20 at 18:27
Never mind, I finally got it to work. It took me forever to realize I needed to use cin.ignore before getline. Thank you for you help tho. – x-reaper Apr 06 '20 at 21:39

C++ binary search with vector of objects

1 Answers1