3
\$\begingroup\$

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));
    }

}
\$\endgroup\$
5
\$\begingroup\$
  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;
    }
\$\endgroup\$
  • 2
    \$\begingroup\$ +1 for [left, right). Should you also eliminate the recursion, it'd be perfect dissection. \$\endgroup\$ – vnp Apr 2 '15 at 0:55
  • 1
    \$\begingroup\$ @vnp Manual tail recursion optimization is left as exercise for readers. Just joking. Non-recursive version is now provided. \$\endgroup\$ – johnchen902 Apr 2 '15 at 1:11
  • 1
    \$\begingroup\$ @Calculus5000 Actually, both implementation has the bug. Even [2, 1] can expose it. Using <= instead of < should fix it. (As shown by my current code) \$\endgroup\$ – johnchen902 Apr 2 '15 at 12:48
  • 1
    \$\begingroup\$ @Calculus5000 Also, I like the first version (with recursion) more. \$\endgroup\$ – johnchen902 Apr 2 '15 at 12:49
  • 1
    \$\begingroup\$ @Calculus5000 A good pivot always divides problem sized n to sub-problem sized n/2 and (n+1)/2, so it will eventually go down to sub-problem sized 1. \$\endgroup\$ – johnchen902 Apr 2 '15 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.