Use binary search if sorted otherwise use linear search

Question

I'm given a problem where the user is given an empty recipe book and they can input and sort the recipes.

I know that a book is sorted if it is empty, has one recipe, and two recipes(ascending/descending). These can use binary search.

But when the user inputs a third recipe it could be either "cookies, donut, turkey" (which is sorted) or "cookies, donut, apples" and that's not sorted. If it's not sorted then I have to use linear search.

This is what I have so far

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

I know what I'm supposed to do, but I don't know how to approach it "code-wise"

Answer 1

Your code says:

mList.sort(comparing);

I believe you've misunderstood what you've been asked to do - assuming that "use binary search if sorted otherwise use linear search", the title of your question, is what you are supposed to do. You are not supposed to sort them at all. This problem requires no knowledge of how to sort things in Java whatsoever.

What you need to understand is searching, not sorting. And how to check whether a sequence of inputs is already sorted.

Now, admittedly, technically you can check if a sequence is already sorted by actually sorting it and then checking if the resulting sequence is in the same order as what you started with. But I wouldn't recommend that.

What I would recommend, instead, is using a Comparator to compare each pair of adjacent elements (if any) in the sequence, to check if the sequence is monotonically increasing or monotonically decreasing.

Answer 2

To find out if a list is sorted, you would have to compare each element with ist neighbors. If only one element of thousands is not in order, a binary search can fail. So you would have to check the complete list. But going through all the list to check if the list is sorted takes longer than to look for one element in the list with linear search, so that makes no sense. Use linear search, if you don't know for sure if a list is sorted or not. That's it.