1

このメソッドは、オブジェクトの配列を渡すことになっています。

Movie[] movieList = new Movie[6];
    movieList[0] = new Drama("Titanic","James Cameron", 1997, 200.0, 80.0, 7.50);
    movieList[1] = new Drama("Fight Club", "David Fincher", 1999, 63.0, 30.0, 6.50);
    movieList[2] = new Animated("Spirited Away", "Hayao Miyazaki", 2001, 19.1, 2.0, 30.0);
    movieList[3] = new Animated("Toy Story", "John Lassater", 1995, 30.0, 3.5, 200.0);
    movieList[4] = new Documentary("Super Size Me","Morgan Spurlock", 2004, 0.006, 35, .005);
    movieList[5] = new Documentary("Jiro Dreams", "David Gelb", 2011, 0.003, 26, .002);

映画のタイトルで整理して検索することになっています。ただし、スイッチステートメントを使用してオブジェクトをメソッドに渡そうとするたびに:

case 3:
    System.out.println("Please input the movie you are searching for:");
    key = input.nextLine();
    key = input.nextLine();
    if(searchMovies(movieList, key)== -1)
    {
        System.out.println("There is no match found for movie with title " + key);
    } 
    else 
    {
        index = (searchMovies(movieList, key));
        System.out.println(movieList[index].toString());
        System.out.println("\n");
    }
    break;

返されるのは、キーが見つからなかったことを示す負の 1 か、配列インデックスが範囲外であることを示すエラーだけです。これは、バブルソートと二分探索法を含む searchMovies メソッドです。

/*-------------------------------------------------------------------------
//searchMovies first sorts the array of objects by title through Bubble
//Sort and then searches the array using Binary Search for the users
//key.
-------------------------------------------------------------------------*/
public static int searchMovies(Movie[] movieList, String key)
{
    //Bubble Sort the titles
    boolean needNextPass = true;
    Movie temp;
    for(int pass=1; pass<movieList.length && needNextPass; pass++)
    {
        needNextPass = false;  // Array may be sorted and next pass not needed
        for(int x=0; x<movieList.length-pass; x++)
            if(((Profitable) movieList[x]).calcProfit() < ((Profitable) movieList[x+1]).calcProfit())  /** compare rental fee */
            {
                temp = movieList[x];
                movieList[x] = movieList[x+1];
                movieList[x+1] = temp;

                needNextPass = true; // Next pass still needed
            }
     }//end for
    //Binary search for key
    int first = 0;
    int last = movieList.length;

    while (first <= last) {
        int mid =(first + last) / 2; // Compute mid point.
        if (key.compareTo(movieList[mid].getTitle()) < 0) {
            last = mid; // repeat search in bottom half.
        } else if (key.compareTo(movieList[mid].getTitle()) > 0) {
            first = mid + 1; // Repeat search in top half.
        } else {
            return mid; // Found it. return position
        }//end if
    }//end loop
    return -1; // Failed to find key
}//end searchMovies'
4

3 に答える 3

0

に基づいてムービーをバブルソートしますcalcProfit()が、次に に基づいて検索しようとしますgetTitle()。

二分検索は、リストの検索に使用している比較関数の観点から、検索しているリストがソートされていると見なされる場合にのみ機能することが保証されています。getTitle()あなたの場合、バイナリ検索を使用できるようにするには、に基づいてリストをソートする必要があります。

さらに、ArrayIndexOutOfBoundsErrorバイナリ検索の最大インデックスを に設定したため、 を取得している可能性がありますmoviesList.length。代わりに設定する必要がありますmoviesList.length-1

于 2013-07-16T10:30:27.280 に答える
0

他の人が示唆したように、バイナリ検索を使用する場合、比較に使用しているキーで配列をソートする必要があります (これはtitleあなたの場合です)。

二分探索アルゴリズムでは、次のようにインデックスを割り当てる方法を変更する必要があります。

int first = 0;
int last = movieList.length - 1; // last index is (length-1) in an array, not length. Trying to access length will produce an `AraryIndexOutOfBounds`

while (first <= last) {
    int mid = (first + last) / 2; 
    if (key.compareTo(movieList[mid].getTitle()) < 0) {
        last = mid - 1;  // Note the -1 here
    } else if (key.compareTo(movieList[mid].getTitle()) > 0) {
        first = mid + 1; 
    } else {
        return mid; 
    }
}

個人的には、アルゴリズムの学習段階にあり、アルゴリズムがどのように機能するかを理解しようとしている場合にのみ、上記のアプローチを使用します。実際のシナリオでは、車輪を再発明する必要がないため、以下のようなものを使用します。

Movie[] movies = ....;

// How our movies are compared to each other? This comparator compares using the titles
Comparator<Movie> titleComparator = new Comparator<Movie>() {
    @Override
    public int compare(Movie o1, Movie o2) {
        return o1.title.compareTo(o2.title);
    }
};

// sort movies by title
Arrays.sort(movies, titleComparator);

String titleToFind = ...
Movie movieToFind = new UnknownMovie(titleToFind);

// perform a binary search to find that movie. If found returns the index
// if not found, returns a negative number that you can use to figure out where this movie should be inserted (see the documentation)
int index = Arrays.binarySearch(movies, movieToFind, titleComparator);

それが役立つことを願っています

于 2013-07-16T11:21:22.000 に答える
0

次の反復を検索するために、半分のどちらを選択するかを決定するtitleために を使用しているため、ムービーの配列は に従ってソートする必要があります。title

于 2013-07-16T10:33:52.550 に答える