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