java - 如果已排序，则使用二分搜索，否则使用线性搜索

Question

我遇到一个问题，即向用户提供一本空的食谱书，他们可以输入食谱并对其进行排序。

我知道如果一本书是空的，有一个食谱和两个食谱(升序/降序)，那么它就会被排序。这些可以使用二分搜索。

但是当用户输入第三个食谱时，它可能是“ cookies 、 donut 、火鸡”(已排序)或“ cookies 、 donut 、苹果”，但未排序。如果它没有排序，那么我必须使用线性搜索。

这就是我目前所拥有的

 public void sortBook(int choice, boolean ascend) {
  RecipeBookComparator comparing = new RecipeBookComparator(choice, ascend);
  mList.sort(comparing);}

public class RecipeBookComparator implements Comparator {
  private int mSortRBook;
  private boolean mAscend;
  public RecipeBookComparator (int choice, boolean ascend) {
     mSortRBook = choice;
     mAscend = ascend;
  }
  public int compare(Object o1, Object o2) {
     Recipe s1 = (Recipe)o1, s2 = (Recipe)o2;
     switch (mSortRBook) {
        case 1:
           if (mAscend == true) {
              int compareName = s1.getName().compareTo(s2.getName());
              if (compareName != 0) {
                 return compareName;
              }
           }
           else {
              int compareName = s1.getName().compareTo(s2.getName());
              if (compareName != 0) {
                 return compareName * -1;
              }
           } ///more cases...

我知道我应该做什么，但我不知道如何“按代码方式”处理它

Answer 1

要确定列表是否已排序，您必须将每个元素与它的邻居进行比较。如果数千个元素中只有一个元素不按顺序排列，则二分查找可能会失败。所以你必须检查完整的列表。但是，遍历所有列表来检查列表是否已排序比使用线性搜索在列表中查找一个元素要花费更长的时间，因此这是没有意义的。如果您不确定列表是否已排序，请使用线性搜索。就是这样。