二进制搜索一直返回-1？

Question

此方法应该通过对象的数组：

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 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' 

Answer 1

你冒泡排序基于calcProfit()你的电影的冒泡排序和二进制搜索方法searchMovies方法，但然后尝试基于getTitle()进行搜索。

只有当您正在搜索的列表被视为按照用于搜索列表的比较函数的角度来考虑排序时，二进制搜索才能保证工作。在你的情况下，该列表必须根据getTitle()进行排序，以便能够使用二分查找。

此外，您可能会得到ArrayIndexOutOfBoundsError的原因是因为您将二进制搜索的最大索引设置为moviesList.length。而是应该将其设置为moviesList.length-1

Answer 2

你的阵列的电影需要根据您的title进行排序，因为你正在使用title决定选择其中的一半，寻找下一次迭代。

Answer 3

正如其他人所建议的，当使用二进制搜索时，您需要按照您用于比较的密钥对数组进行排序（在您的情况下，这将是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); 

希望帮助