So I had an assignment where we were to write a method that finds the smallest number in a list and returns where it's located (position). The list is sorted but can be shifted. [7, 8, 9, 0, 1, 2, 3, 4, 5, 6] for example.

My solution looks like this:

public class Main
{
    
    public static <E extends Comparable<E>> int findMinIndex(E[] a) {
      if(a.length == 0){
        return -1;
      }else{
        return _findMinIndex(a, 0, a.length - 1);
      }
    }

    private static <E extends Comparable<E>> int _findMinIndex(E[] a, int first, int last){
      if(last == 0){
        return last;
      }
      int mid = first   (last - first) / 2;
      if(mid == 0 || mid == last){
          return mid;
      }

      if(a[mid].compareTo(a[last]) < 0){
          if(last - first == 1){
              return mid - 1;
          }

          return _findMinIndex(a, first, mid);
      }else{
        if(last - first == 1){
            return mid   1;
        }

        return _findMinIndex(a, mid, last);
      }
    }
    
    public static void main(String[] args) {
        Integer[] a = {2, 13, 17, 23, 30, 35, 41, 45, 53, 67};
        System.out.println(findMinIndex(a));
    }
}

They want us to practice generic classes so that's why it takes a generic array.

Output should be 0 since 2 is smallest. Now this passed all test cases but I think it may seem to have a bit too many special cases, is there a more efficient way to write this?

CodePudding user response：

When i read your implementation, i had the same thought as you described it: too many special cases.

If i understand the task correctly, the input is sorted in ascending order (lowest value at lowest index, highest value at highest index), but might be shifted.

When you say "a more efficient way to write this", i assume that you don't mean runtime efficiency, but less code complexity.

package stackoverflow;

/**
 * https://stackoverflow.com/questions/71399165/
 */
public class LocateSmallestValue {

    public static void main(String[] args) {
        Integer[] a1 = { 7, 8, 9, 0, 1, 2, 3, 4, 5, 6 };
        System.out.println("a1: "   findMinIndex(a1));
        Integer[] a2 = { 2, 13, 17, 23, 30, 35, 41, 45, 53, 67 };
        System.out.println("a2: "   findMinIndex(a2));
        Integer[] a3 = { 2, 3, 4, 5, 6, 7, 8, 9, 0, 1 };
        System.out.println("a3: "   findMinIndex(a3));
        Integer[] a4 = { 67, 2, 13, 17, 23, 30, 35, 41, 45, 53 };
        System.out.println("a4: "   findMinIndex(a4));
        Integer[] a5 = { 2, 3, 4, 5, 6, 1 };
        System.out.println("a5: "   findMinIndex(a5));
    }

    /**
     * @param input The input is sorted but can be shifted. [7, 8, 9, 0, 1, 2, 3, 4, 5, 6] for example.
     * @return index of smallest value
     */
    public static <E extends Comparable<E>> int findMinIndex(E[] input) {
        if (input.length == 0) {
            throw new IllegalArgumentException("input array is empty");
        }
        // This case handles an input that is not shifted.
        if (input[0].compareTo(input[input.length - 1]) <= 0) {
            return 0;
        }
        return _findMinIndex(input, 0);
    }

    private static <E extends Comparable<E>> int _findMinIndex(E[] input, int currentIndex) {
        int nextIndex = currentIndex   1;
        E currentValue = input[currentIndex];
        E nextValue = input[nextIndex];
        if (currentValue.compareTo(nextValue) > 0) {
            return nextIndex;
        }
        return _findMinIndex(input, nextIndex);
    }

}

Output:

a1: 3
a2: 0
a3: 8
a4: 1
a5: 5

CodePudding user response：

Here is a solution using a binary search that uses a slightly different check for keying on the target. Given an array of values sorted in ascending order, any group of values between any two points within a rotated array will not contain the target value if that group is also sorted in ascending order. This is because the target value must lie in a group where the array transitions from descending to ascending. Whether a group within a rotated array is sorted is easily determined by comparing the first and last values of that group.

Using that fact, the array is simply continually subdivided into groups until the left most index of a group exceeds the right most index. At that point, the right most index or high point contains the target value and is returned as the solution.

public static int findMinIndex(Integer[] a) {
    int low = 0;
    int high = a.length-1;
    // check if the array is un-rotated.
    if (a[low] < a[high]) {
        return 0;
    }
    int mid = high/2;
    while (low < mid) {
        if (a[low].compareTo(a[mid]) > 0) {
            // It's in this range
            high = mid;
        } else {
            low = mid;
        }
        mid = low   (high-low)/2;
    }
    return high;
}

Here is how I tested it.

• create an array of N sorted random values between 1 and 1000.
• assign A[0] to min.
• the iterate over N rotating the previous array by 1 each time
• in all cases, the index for the minimum value was found.

int N = 10_000;
Random r = new Random();
Integer[] a = r.ints(N,1, 1000).boxed().sorted().toArray(Integer[]::new);
Integer min = a[0];
for (int i = 0; i < N; i  ) {
    int index = findMinIndex(a);
    if (a[index] != min) {
        System.out.printf("Error at index %d - %d found!%n", index, a[index]);
    }
    Collections.rotate(Arrays.asList(a), 1);
}

Note: Arrays.asList returns a list backed by the supplied Object array. So Collections.rotate can be used to rotate the array. This will not work for primitive arrays.