current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

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

}
share|improve this question

1 Answer 1

up vote 5 down vote accepted
  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;
    }
share|improve this answer
2  
+1 for [left, right). Should you also eliminate the recursion, it'd be perfect dissection. –  vnp yesterday
1  
@vnp Manual tail recursion optimization is left as exercise for readers. Just joking. Non-recursive version is now provided. –  johnchen902 yesterday
1  
@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) –  johnchen902 16 hours ago
1  
@Calculus5000 Also, I like the first version (with recursion) more. –  johnchen902 16 hours ago
1  
@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. –  johnchen902 16 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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