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\$

1 Answer 1

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\$
7
  • 2
    \$\begingroup\$ +1 for [left, right). Should you also eliminate the recursion, it'd be perfect dissection. \$\endgroup\$
    – vnp
    Apr 2, 2015 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\$ Apr 2, 2015 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\$ Apr 2, 2015 at 12:48
  • 1
    \$\begingroup\$ @Calculus5000 Also, I like the first version (with recursion) more. \$\endgroup\$ Apr 2, 2015 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\$ Apr 2, 2015 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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