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);

并且应该按电影的标题来组织和搜索。但是，每次我尝试使用 switch 语句将对象传递给方法时：

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，因为您正在使用title来决定选择哪一半，以搜索下一次迭代。

于 2013-07-16T10:33:52.550 回答
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 回答