# Find minimum element in a rotated array

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

}


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

• +1 for [left, right). Should you also eliminate the recursion, it'd be perfect dissection.
– vnp
Commented Apr 2, 2015 at 0:55
• @vnp Manual tail recursion optimization is left as exercise for readers. Just joking. Non-recursive version is now provided. Commented Apr 2, 2015 at 1:11
• @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) Commented Apr 2, 2015 at 12:48
• @Calculus5000 Also, I like the first version (with recursion) more. Commented Apr 2, 2015 at 12:49
• @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. Commented Apr 2, 2015 at 12:58