Find minimum element in a rotated array

Question

Here's an implementation of finding the minimum element in a rotated array using binary search (one that is sorted in ascending order, and all elements are distinct).

Please let me know of any improvements that can be made to it.

import java.util.List;

public class RotatedArray {
    /**
     * Finds and returns the index at which the smallest value in a rotated array is located.
     *
     * @param rotatedArray    a rotated array that's sorted in ascending order (all elements are distinct)
     * @return the index of the smallest value, or -1 if rotatedArray is empty
     */
    public int findReset(List<Integer> rotatedArray) {
        if (rotatedArray.isEmpty()) {
            return -1;
        }

        // when array is already sorted
        if (rotatedArray.size() == 1 || rotatedArray.get(0) < rotatedArray.get(rotatedArray.size() - 1)) {
            return 0;
        }

        int midpoint = rotatedArray.size() / 2;

        // when left side is monotonically increasing
        if (rotatedArray.get(0) < rotatedArray.get(midpoint)) {
            return findReset(rotatedArray.subList(midpoint + 1, rotatedArray.size())) + midpoint + 1;
        }

        // Prevents stack overflow error from occurring (e.g. test case [1,2,3,4,0])
        if (rotatedArray.size() == 2) {
            return midpoint;
        }

        // when right side is monotonically increasing
        return findReset(rotatedArray.subList(0, midpoint + 1));
    }

}

Answer 1

1. The method should be static.
2. The method should throw NoSuchElementException when the list is empty.
3. I prefer to index by [left, right) instead of using subList
4. Choose a good pivot location, and you don't need the size() == 2.

In code:

    public static int findReset(List<Integer> rotatedArray) {
        if (rotatedArray.isEmpty()) {
            throw new NoSuchElementException("No reset for an empty list");
        }
        return findReset0(rotatedArray, 0, rotatedArray.size());
    }
    private static int findReset0(List<Integer> rotatedArray, int left, int right) {
        // when array is already sorted
        if(left + 1 == right || rotatedArray.get(left) < rotatedArray.get(right - 1))
            return left;
        int middle = (left + right) / 2;
        if (rotatedArray.get(left) <= rotatedArray.get(middle - 1)) {
            // when left side is monotonically increasing
            return findReset0(rotatedArray, middle, right);
        } else {
            // when right side is monotonically increasing
            return findReset0(rotatedArray, left, middle);
        }
    }

Here is a version with manual tail recursion optimization:

    public static int findReset(List<Integer> rotatedArray) {
        if (rotatedArray.isEmpty()) {
            throw new NoSuchElementException("No reset for an empty list");
        }
        int left = 0, right = rotatedArray.size();
        while(left + 1 < right && rotatedArray.get(left) >= rotatedArray.get(right - 1)) {
            int middle = (left + right) / 2;
            if (rotatedArray.get(left) <= rotatedArray.get(middle - 1)) {
                // when left side is monotonically increasing
                left = middle;
            } else {
                // when right side is monotonically increasing
                right = middle;
            }
        }
        return left;
    }