javaarraysbinary-search

Binary Search for year of songs in array of songs


I'm trying to get the code to search for a songs that were made in a specific year

I've tried implementing my own binary search code but it's not printing out all of the songs made in that year, just one Class:

 public class MusicV3
{
// instance variables
private int year;
private String title;
private String artist;

// Constructor for objects of class Music
public MusicV3(String t, int y, String a)
{
    // initialize instance variables
    title = t;
    year = y;
    artist = a;
}

public String getTitle()
{
    return title;
}

public void setTitle(String t)
{
    title = t;
}

public String getArtist()
{
    return artist;
}

public void setArtist(String a)
{
    artist = a;
}

public int getYear()
{
    return year;
}

public void setTitle(int y)
{
    year = y;
}

public String toString()
{
    String str = String.format( "%-25s %4d   %-20s ", title,  year , artist);
    return str;
}
}

Tester class:

 public class MusicV3Tester2{
 public static void main(String[]args)
 {
    int find = 0;
    MusicV3[] songs = new MusicV3[10];
    MusicV3[] sortedSongs = new MusicV3[songs.length];
    songs[0] = new MusicV3("Sugar", 2014, "Maroon 5");
    songs[1] = new MusicV3("Mercy", 2016, "Shawn Mendes");
    songs[2] = new MusicV3("Shape of You", 2017, "Ed Sheeran");
    songs[3] = new MusicV3("Photograph", 2014, "Ed Sheeran");
    songs[4] = new MusicV3("Closer", 2016, "The Chainsmokers");
    songs[5] = new MusicV3("Galway Girl", 2017, "Ed Sheeran");
    songs[6] = new MusicV3("Counting Stars", 2013, "OneRepublic");
    songs[7] = new MusicV3("7 Years", 2015, "Lukas Graham");
    songs[8] = new MusicV3("Night Changes", 2014, "One Direction");
    songs[9] = new MusicV3("What Makes You Beautiful", 2011, "One Direction");

    printSongs(songs);
    System.out.println();

    sortedSongs = sortByYear(songs);
    System.out.println("Song list sorted by year:");
    //printSongs(sortedSongs);
    System.out.println();

    System.out.println("Searching for the year: 2000");
    find = findYear(songs, 2000);
    if(find != -1){
        System.out.println("We found songs made in the year 2000 in the song list: ");
        System.out.println(sortedSongs[find]);
    }
    else
        System.out.println("Songs made in the year 2000 are not in the song list");
    System.out.println();

    System.out.println("Searching for the year: 2014");
    find = findYear(songs, 2014);
    if(find != -1){
        System.out.println("We found songs made in the year 2014 in the song list: ");
        System.out.println(sortedSongs[find]);
    }
    else
        System.out.println("Songs made in the year 2014 are not in the song list");
    System.out.println();
}

public static void printSongs(MusicV3[] s)
{
    System.out.println("Song                      Year   Artist");
    System.out.println("-------------------------------------------------------");
    for(int i = 0; i < s.length; i++)
        System.out.println(s[i]);
    }

public static MusicV3[] sortByYear(MusicV3 [] movies){
    MusicV3[] sortedList = movies;
    int i;
    int k;
    int posmax;
    MusicV3 temp;
    for ( i = movies.length - 1 ; i >= 0 ; i-- )
    {
       posmax = 0;
         for ( k = 0 ; k <= i ; k++ )
         {
             if (movies[k].getYear()> movies[posmax].getYear())
             posmax = k;
            }

            temp = movies[i];
            movies[i] = movies[posmax];
            movies[posmax] = temp;
}
return sortedList;
}

public static int findYear(MusicV3[] songs, int year){
 int high = songs.length;
 int low = -1;
 int probe;

 while (high - low > 1)
 {
 probe = ( high + low ) / 2;
if (songs[probe].getYear() > year)
  high = probe;
else 
 low = probe;
} 

if(low >= 0 && songs[low].getYear() == year){
    return low;
}
else{
return -1;
}
}

}

It's supposed to get all songs made in the year 2000 and 2014 from the array but for some reason the search for 2000 is right but not 2014, it just says there are is only one song made in 2014 when there are several


Solution

  • It looks like you don't check if songs[probe].getYear() == year during the while-loop in findYear.

    Maybe:

    public static int findYear(MusicV3[] songs, int year) {
        int high = songs.length;
        int low = -1;
        int probe = -1;
    
        while (high - low > 1) {
            probe = (high + low) / 2;
            int probeSongYear = songs[probe].getYear();
    
            if (probeSongYear == year) {
                break;
            } else if (probeSongYear > year)
                high = probe;
            else
                low = probe;
        }
    
        if (probe >= 0 && songs[probe].getYear() == year) {
            while (songs[--probe].getYear() == year) {
            }
            return probe + 1;
        }
    
        return -1;
    }
    

    Don't forget to add "find =" like below:

        System.out.println("Searching for the year: 2014");
        find = /* <--- ADD THIS */ findYear(songs, 2014);
    

    To print all the songs (as requested in comment) for the year in question:

        System.out.println("Searching for the year: 2014");
        find = findYear(songs, 2014);
        if (find != -1) {
            System.out.println("We found songs made in the year 2014 in the song list: ");
            while (sortedSongs[find].getYear() == 2014) {
                System.out.println(sortedSongs[find++]);
            }
        }