Использовать двоичный поиск, если сортировка в противном случае использует линейный поиск

Question

У меня возникает проблема, когда пользователю предоставляется пустая книга рецептов, и они могут вводить и сортировать рецепты.

Я знаю, что книга сортируется, если она пуста, имеет один рецепт и два рецепта (восходящий/нисходящий). Они могут использовать двоичный поиск.

Но когда пользователь вводит третий рецепт, он может быть «куки, пончик, индейка» (который сортируется) или «куки, пончик, яблоки», и это не сортируется. Если он не отсортирован, я должен использовать линейный поиск.

Это то, что я до сих пор

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

Ваш код говорит :

mList.sort (сравнение);

Я считаю, что вы поняли, что вы попросили сделать - если предположить, что «использовать бинарный поиск, если отсортирован в противном случае использовать линейный поиск», название вашего вопроса, является то, что вы должны делать. Вы не должны сортировать их вообще. Эта проблема не требует знания того, как сортировать вещи в Java вообще.

Что вам нужно знать, это поиск, а не сортировка. И как проверить, отсортирована ли последовательность входов.

Теперь, по общему признанию, технически вы можете проверить, отсортирована ли последовательность, фактически сортируя ее, а затем проверяя, соответствует ли полученная последовательность тем же порядком, с которой вы начали. Но я бы не рекомендовал этого.

Что я бы рекомендовал вместо этого использовать компаратор для сравнения каждой пары смежных элементов (если есть) в последовательности, чтобы проверить, монотонно ли монотонно возрастает или монотонно уменьшается последовательность.

Answer 2

Чтобы узнать, отсортирован ли список, вам нужно будет сравнить каждый элемент с сотами ist. Если только один элемент тысяч не в порядке, двоичный поиск может завершиться неудачей. Поэтому вам нужно будет проверить полный список. Но просмотр всего списка для проверки сортировки списка занимает больше времени, чем поиск одного элемента в списке с линейным поиском, поэтому это бессмысленно. Используйте линейный поиск, если вы точно не знаете, отсортирован ли список или нет. Вот и все.